2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "Not an integer multiple of another point" means the coordinates have greatest common divisor $1$. $\endgroup$ – GEdgar Apr 16 at 22:19
  • $\begingroup$ 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. $\endgroup$ – Cogitator Apr 16 at 22:22
2
+50
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Cogitator Apr 16 at 23:52
  • $\begingroup$ I expanded my answer to make you convinced that the key is the Farey sequence and thus the Totient function. $\endgroup$ – G Cab Apr 17 at 15:29
  • $\begingroup$ 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. $\endgroup$ – Cogitator Apr 17 at 17:34
  • $\begingroup$ @Cogitator: well, honestly, the extension to higher dim. is not so straight. I found a precious article giving the formulas for that. $\endgroup$ – G Cab Apr 20 at 16:39
  • $\begingroup$ 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. $\endgroup$ – Cogitator Apr 23 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.