How many points in a uniform n-dimensional grid can't be expressed as an integer multiple of another point in the grid?

225 Views Asked by At

Suppose I have an $n$-dimensional uniform grid. Along each axis I have points from $0$ to some integer extent $L$.

Is there a closed form for the number of points that can't be expressed as a non-zero, integer multiple of another point in the grid, given $n$ and $L$?

For instance, in the 2D case for $L=10$:

$[2,1]$ would satisfy the condition but $[4,2]$ would not because it is an integer multiple of $[2,1]$.

A possibly helpful note:

If you already know the smallest vector along a possible direction in the grid, you can find how many other points along the same direction there are. So for the point $[2,1]$ I know there are

$$ \left\lfloor\left(\frac{L}{\max\{x,y\}}\right)\right\rfloor-1=\left\lfloor\left(\frac{10}{2}\right)\right\rfloor-1=4 $$

integer multiples of $[2,1]$. But if I knew those points a priori I wouldn't need to solve this problem.

1

There are 1 best solutions below

9
On BEST ANSWER

In 2D your problem is related to the Farey sequence.
In fact the geometrical rendering of this sequence is as sketched below.

Farey_geom_1

At level $7$ for example, you have all the ratios already contained in precedent levels (the small black points) plus the newly added (big red points) $1/7, 2/7, \cdots, 6/7$.

In the Wikipedia article above you find all the explanation of how to count the number of terms in a Farey sequence of a certain level,
as well the difference with the previous levels, and I am not going to repeat it here.

As a matter of fact, in 2D a segment from the origin to the point$(X,Y)$ (assume wlog $0 \le Y \le X$) will not intercept an intermediate point with integral coordinates if the fraction $Y/X$ is irreducible, i.e. if $\gcd (Y,X) =1$ , otherwise if $1 < \gcd (Y,X) =g$ then $(X,Y) = g (X/g, Y/g)$.
Also consider that $\gcd(Y,X) =\gcd(Y, X-Y)$, that is we can tilt the triangle above to have the right corner at the origin and count the points by diagonals $X+Y=n$.

Similarly in 3D, a segment from the origin to the point $(X,Y,Z)$ will not intercept any other point before if $\gcd(X,Y,Z)=1$, otherwise we will have $(X,Y,Z)= g (X/g, Y/g, Z/g)$.

Same for higher dimensions, and again we can count the points by diagonal planes $$ \eqalign{ & \left\{ {\left( {X_1 ,X_2 , \cdots ,X_m } \right)\;:\;\gcd \left( {X_1 ,X_2 , \cdots ,X_m } \right) = g\; \wedge \;\;0 \le X_1 \le X_2 \le \cdots \le X_m \le L} \right\} = \cr & = \left\{ {\left( {X_1 ,X_2 , \cdots ,X_m } \right)\;:\;\gcd \left( {X_1 ,X_2 , \cdots ,X_m } \right) = g\; \wedge \;\;0 \le X_1 + X_2 + \cdots + X_m \le L} \right\} \cr} $$

The problem goes under the standard denomination of visible lattice points.

At the same time we can consider $$ \left\{ {\left( {X_1 ,X_2 , \cdots ,X_m } \right)\;:\;\quad \gcd \left( {X_1 ,X_2 , \cdots ,X_m } \right) = 1\; \wedge \;\;X_1 + X_2 + \cdots + X_m = n} \right\} $$ as the set of the Compositions of $n$ into $m$ relatively prime parts,
the compositions being understood in the "weak" sense if $0 \le X_j$ and in the standard sense with $1 \le X_j$ .

Under this perspective, take a look at this interesting work by H.W. Gould
"Binomial Coefficients, the Bracket Function, and Compositions with Relatively Prime Summands".
Therein, having denoted by $ R_{\,m} (n)$ the number of standard compositions as above, i.e: $$ R_{\,m} (n) = \sum\limits_{\left\{ {\matrix{ {1\, \le \,X_k } \cr {\gcd \left( {X_1 ,X_2 , \cdots ,X_m } \right) = 1} \cr {X_1 + X_2 + \cdots + X_m = n} \cr } } \right.} 1 $$ it is demonstrated that $$ \bbox[lightyellow] { R_{\,m} (n) = \sum\limits_{d\backslash n} {\left( \matrix{ d - 1 \cr m - 1 \cr} \right)\mu \left( {n/d} \right)} }$$ where $\mu$ denotes the Möbius function.

Example:

in 2D, the formula above gives $$ R_{\,2} (n)\quad \left| {\;2 \le n} \right.\;\; = \varphi (n) = {\rm 1}{\rm , 2}{\rm , 2}{\rm , 4}{\rm , 2}{\rm , 6}{\rm , 4}{\rm , 6}{\rm , 4}{\rm ,} \cdots $$

in 3D, we get $$ R_{\,3} (n)\quad \left| {\;3 \le n} \right.\;\; = {\rm 1}{\rm , 3}{\rm , 6}{\rm , 9}{\rm , 15}{\rm , 18}{\rm , 27}{\rm , 30}{\rm , 45}{\rm , 42}{\rm , 66}{\rm , 63}{\rm , 84}{\rm , 84} {\rm , 120}{\rm , 99} $$ which is OEIS A000741

in 4D it is OEIS A000742