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

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]$$.

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.

• "Not an integer multiple of another point" means the coordinates have greatest common divisor $1$. – GEdgar Apr 16 at 22:19
• Right. Which means it's easy to check if any given point satisfies the condition, but given some large dimensional space, I want to see how many points satisfy the condition without looping through them all and checking. – Cogitator Apr 16 at 22:22

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

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

• I think you may be right. I think in 2D the number of allowed points is related to the number of terms in the Lth Farey sequence. – Cogitator Apr 16 at 23:52
• I expanded my answer to make you convinced that the key is the Farey sequence and thus the Totient function. – G Cab Apr 17 at 15:29
• Yes. I am now convinced the key is the Farey series and I have the answer for 2D. Still trying to work out the solution for higher dimensions. – Cogitator Apr 17 at 17:34
• @Cogitator: well, honestly, the extension to higher dim. is not so straight. I found a precious article giving the formulas for that. – G Cab Apr 20 at 16:39
• I haven't fully review the article yet, but I'm sufficiently convinced that this is close enough to the right track to award the bounty. Thanks. – Cogitator Apr 23 at 13:58