10
$\begingroup$

Let $v$ be the vector $[a_1,a_2,\ldots,a_n]$ where the $a_i$'s are positive integers with $\gcd(a_1,\ldots, a_n)=1$. Let $C$ be the hypercube $[0,1]\times [0,1]\times \cdots \times [0,1]$ in $\mathbb{R}^n.$ Imagine the line given by $vt$ as $t$ runs through the real numbers mod $1$, by which I mean that as the line leaves $C$, it re-appears on the opposite face and continues. This is a periodic operation, since the $a_i$'s are integers. So $C$ is filled with lines.

Now given $M$, partition $C$ into $M^n$ sub-cubes, $[b_1/M,(b_1+1)/M]\times \cdots [b_n/M,(b_n+1)/M]$, where the $b_i$'s range over $0,1,2,\ldots M-1$.

I would like conditions on the vector $v$ which guarantee that the line visits every sub-cube. I've tried all sorts of Diophantine approximation things, but the only clear result I get is for $n=4$. It would be most helpful is the conditions left only finitely many $v$ for which the line didn't visit all sub-cubes.

Stand by for a bounty in a couple days.

Edit: Some background. There is a function $F$ of $n$ variables which is periodic of period one (in all variables.) $F$ has some zeros scattered about the $n$-dimensional cube. I would like to bound $F(vt)$ away from zero. To this end, I'm hoping for a condition that tells me when the line $vt$ is forced to be close to a zero (and when it is far away.) In my comment, I said I "hoped" for only finitely many, but I know that's a pipe dream. (Although I can do it for $n=4$.) Still, there must be a way to quantify how "messy" the periodic line is in the $n$-dimensional cube, based on some gcd-ish conditions on the components of $v$...?

Another edit: In this paper:

http://www.ams.org/journals/proc/1992-116-02/S0002-9939-1992-1101984-4/S0002-9939-1992-1101984-4.pdf

On the page numbered 315, Lemma 1, I give a criterion (basically part ii)) that guarantees that the line is dispersed "uniformly" enough in the cube in the $4$-dimensional case. The purpose of this question is to find the equivalent criterion for $n>4$. My paper shows that only finitely many such vectors \emph{don't} spread "uniformly" around the cube, and then I'm able to compute the answer to my question. Besides applying to Newman polynomials, I think this technique would extend to more popular polynomials, such as the Littlewood.

$\endgroup$
  • $\begingroup$ There are infinitely many vectors $v$ such that the line misses at least one cube. If $v$ is of the form $v = (a, b, a+b)$, for instance, then the line lies on the plane $x + y - z \in \mathbb{Z}$, which is not dense in $\mathbb{R}^3 / \mathbb{Z}^3$. $\endgroup$ – Dongryul Kim Nov 26 '16 at 22:10
  • $\begingroup$ Must the vectors intersect strictly the interiors of the sub-cubes? E.g., let $n=2, v=(a,b), m=2$; does $v$ trivially intersect every sub-cube just by virtue of the fact that $(0,0)$ is a member of each of the four sub-cubes when taken mod $(1,1)$? $\endgroup$ – Chas Brown Nov 26 '16 at 23:10
  • $\begingroup$ @ChasBrown No. They can intersect the boundaries. And "yes" to the second question. $\endgroup$ – B. Goddard Nov 27 '16 at 18:46
  • $\begingroup$ you mean, evidently, to say the line $x_k=mod(a_k t,\;1)$ $\endgroup$ – G Cab Nov 28 '16 at 14:53
  • $\begingroup$ @GCab If I understand your notation correctly, yes. $\endgroup$ – B. Goddard Nov 28 '16 at 17:04
5
+250
$\begingroup$

So my understanding is that we are considering the line (segments) given by $$ \left\{ \begin{gathered} x_{\,1} = a_{\,1} \;t\;\bmod 1 = \left\{ {a_{\,1} \;t} \right\} \hfill \\ x_{\,2} = a_{\,2} \;t\;\bmod 1 = \left\{ {a_{\,2} \;t} \right\} \hfill \\ \quad \vdots \hfill \\ x_{\,n} = a_{\,n} \;t\;\bmod 1 = \left\{ {a_{\,n} \;t} \right\} \hfill \\ \end{gathered} \right.\quad \Rightarrow \quad \mathbf{x} = \left\{ {\mathbf{a}\;t} \right\}\quad \left| \begin{gathered} \;a_{\,k} \in \;\;\mathbb{Z}\,_ + \; \hfill \\ \;\gcd (a_{\,1} ,\, \cdots ,a_{\,n} ) = 1 \hfill \\ \end{gathered} \right. $$ where $\left\{x \right\}$ is the fractional part of $x$, i.e. $$ \left\{ x \right\} = x - \left\lfloor x \right\rfloor $$ and either it and the floor function are assumed to apply to vectors component-wise.

That premised, let us invert the scheme:
consider the space partitioned into a lattice of hyper-cubes with unitary sides and let the line "free" to run across the space, i.e. across the cubes of the n-D lattice.
We will individuate each cube according to the floor of the coordinates of the points it contains, that is according to $\left\lfloor \mathbf{x} \right\rfloor $, which are the coordinates of its lower vertex. That also means that each cube so individuated will include the faces with lower coordinates and exclude the others.

Starting from the origin, the line will traverse the cube $(0,\, \cdots ,\, 0)$ and continue across the others.
If in traversing a cube, the line segment within it has the same relative coordinates as the segment from the origin, then it will individuate a cycle, same as in the original scheme proposed.
Relative coordinates same as the segment from the origin, means a relative $(0,\, \cdots ,\, 0)$ point of origin of the segment, i.e. a point with integral coordinates.

Therefore we are looking for the values of the parameter $t$ such that $$ \left\{ {\mathbf{a}\;t} \right\} = \mathbf{0}\quad \Rightarrow \quad \left\{ {t\;\gcd (a_{\,1} ,\, \cdots ,a_{\,n} )} \right\} = 0\quad \Rightarrow \quad \left\{ t \right\} = 0\quad \Rightarrow \quad t \in \;\;\mathbb{Z}\; $$ We will have a repetition at each block $t \, (a_{\,1} ,\, \cdots ,a_{\,n} )$.
The number of blocks that the line traverses from the origin till the point at $t=1$ (excluded) will correspond, in the original scheme, to the number of distinct segments inside the cube.
We have a boundary cross whenever one of the components of $\left\{ {\mathbf{a}\;t} \right\}$ gets null, and $$ \begin{gathered} \left\{ {a_{\,k} \;t} \right\} = 0\quad \left| {\;0 \leqslant t < 1} \right.\quad \Rightarrow \quad \hfill \\ \Rightarrow \quad t \in \left\{ {0,\;\;\frac{1} {{a_{\,1} }},\; \cdots ,\;\frac{{a_{\,1} - 1}} {{a_{\,1} }},\;\;\frac{1} {{a_{\,2} }},\; \cdots ,\;\frac{{a_{\,2} - 1}} {{a_{\,2} }},\; \cdots \; \cdots \;,\frac{1} {{a_{\,n} }},\; \cdots ,\;\frac{{a_{\,n} - 1}} {{a_{\,n} }}} \right\} = \hfill \\ = \left\{ {t_{\,0} = 0,\;\;t_{\,1} = \frac{1} {{a_{\,n} }},\;\;t_{\,2} ,\; \cdots \;,\;\;t_{\,q} } \right\}\quad \left| {\,a_{\,n} = \max \left( {a_{\,1} ,\; \cdots ,\;a_{\,n} } \right)} \right. \hfill \\ \end{gathered} $$ We may assume, WLOG, that the components of $\mathbf a$ are in non-decreasing order. Since it might be that $\gcd (a_{\,k} ,a_{\,j} \ne 1$, for $k, j$ ranging from $1$ to $n$, some of the values for $t$ might be coincident, and the above expression shall be understood in fact as a set.
If $\gcd (a_{\,k} ,a_{\,j} = m$ then the corresponding sub-sets will have $m-1$ elements in common, so the cardinality of the set depends from the mutual $\gcd$s between the components of $\mathbf a$.

However we have that
number of crossings = number of different segments in the original scheme (apart the $0$) $q \leqslant -n+ a_{\,1} + a_{\,2} + \, \cdots + a_{\,n} $

If the components of $\mathbf a$ were in the arithmetic sequence $(b+1,\; \cdots ,\;b+n)$, then we could apply to the Farey sequence and tell that the the No. of values of $t$ be $$ q = \sum\limits_{b + 1\, \leqslant \,k\, \leqslant \,b + n} {\varphi (k)} $$ with $\varphi$ being the Euler Totient function.
In any case, the Farey's sequence tells us that the $t_{k}$ values , apart $0$, are symmetric with respect to $1/2$, and that $q$ is odd or even depending on whether $1/2$ is included or not in the set.

Line_in_Box

The example sketched above ($\mathbf a =(2,3,5)$) helps to visualize the process involved.
The line enters a cube of the lattice at $t_{k} \mathbf a$ and leaves it at $t_{k+1} \mathbf a$.
The relevant segment is translated back by $\left\lfloor {t_{\,k} \,\mathbf{a}} \right\rfloor $ to the reference cube at the origin. During the translation, the segment remains parallel to $\mathbf a$ and thus orthogonal to any of the vectors normal to $\mathbf a$.
The configuration inside the refence cube of the $q+1$ segments (including the last $t_{q},1$) will be symmetric with respect to the $(0,0, \cdots ,0)$ and $(1,1, \cdots, 1)$ vertices. They will lay on planes parallel to $\mathbf a$.
Let call $\mathbf b$ one of the vectors normal to $\mathbf a$, then

$$ \begin{gathered} \mathbf{b} \cdot \mathbf{a} = 0\quad \Rightarrow \quad \mathbf{b} \cdot \left( {t\,\mathbf{a}} \right) = 0\quad \Rightarrow \quad \mathbf{b} \cdot \left( {t_{\,k} \,\mathbf{a}} \right) = 0\quad \Rightarrow \hfill \\ \Rightarrow \quad \mathbf{b} \cdot \left\{ {t_{\,k} \,\mathbf{a}} \right\} = - \,\mathbf{b} \cdot \left\lfloor {t_{\,k} \,\mathbf{a}} \right\rfloor \hfill \\ \end{gathered} $$

and all a cascade of relations.
For our scope we shall seek for the vector $\mathbf b$ that minimizes the set of values corresponding to $\mathbf{b} \cdot \left\lfloor {t_{\,k} \,\mathbf{a}} \right\rfloor$ at the varing of $k$. This will minimize the number of planes containing the points, and thus provide the largest separation between them, which in turn will determine the maximum $M$ as requested.
Since the $t_k$ are rational, we may restrict the search to the vectors with integral components.
By conducting this exercise on a few examples, it comes evident and it is intuitive ( without pretending to constitute a rigorous proof ) that the vector in question is the one that

gives $\mathbf{b} \cdot \mathbf{a} = 0$ and has minimum modulus

and this is the vector provided by the Multidimensional Extended Euclidean Algorithm, which is connected to the Bezout Identity.
It is to remember in fact that in 2D the algorithm provides $\gcd (a,b) = n_{\,k} \,a + m_{\,k} \,b\quad 0 = n_{\,k + 1} \,a + m_{\,k + 1} \,b$ and either $\left( {n_{\,k} ,\;\,m_{\,k} } \right)$ and $\left( {n_{\,k+1} ,\;\,m_{\,k+1} } \right)$ have minimum modulus.
Finally $c= \mathbf{b} \times \mathbf{a}$ will give the separation among the segments in the same plane.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is helpful, but I wish I knew how uniformly the segments were distributed around the cube. $\endgroup$ – B. Goddard Nov 30 '16 at 17:04
  • $\begingroup$ @B.Goddard: once you have the set of values for $t$, then you have all the information to individuate the segments, e.g. their starting (entry) point on the cube at the origin, and since their orientation is defined, thus their distance from the origin, from the axis through the origin and oriented as $\mathbf a$, etc. Now, by "how uniformly .. around the cube", do you mean by which criteria ? $\endgroup$ – G Cab Nov 30 '16 at 20:08
  • $\begingroup$ I'd like to be able to say that every point in the cube is within epsilon of some point on the line. "Uniformly" in the sense that every subcube is visited by the line. $\endgroup$ – B. Goddard Nov 30 '16 at 20:47
  • $\begingroup$ I see: not really easy to put in algebraic terms, but a SW algorithm compact enough could be possible, would be that ok for your needs? $\endgroup$ – G Cab Nov 30 '16 at 23:22
  • $\begingroup$ So you get that a necessary condition for the line to visit all $M^n$ little cubes is that $a_1+a_2+\cdots+a_n\ge M^{n-1}$? $\endgroup$ – Jyrki Lahtonen Dec 1 '16 at 15:21
0
$\begingroup$

If you're looking for a sufficient condition, you may take $v$ as $[1,M,M^2,...,M^{n-1}]$, it passes trough all the squares $(b_1,...,b_n)$, $b_i\in\{0,...,M-1\}$

Proof: Look at the vector $u=(b_1M^{-1}+b_2M^{-2}+...+b_nM^{-n}+oM^{-n-1})v$ its coordinates are $$[b_1M^{-1}+b_2M^{-2}+...+b_nM^{-n}+oM^{-n-1}, b_1+b_2M^{-1}+...+b_nM^{-n+1}+oM^{-n},..., b_1M^{n-2}+b_2M^{M-3}+...+b_nM^{-1}+oM^{-2} ]$$ All are integers plus a number from $(b_i/M,(b_i+1)/M)$

In order to generalize it, $a_i$ doesn't have to be $M^{i-1}$, it may be any number $(a_i\equiv k_iM^{i-1}\mod M^n)$ where $k_i<M$ and $gcd(k_i,M)=1$.

And of course any permutation of $a_i$s is possible

In addition, you said "I'd like to be able to say that for a given M, only finitely many such vectors fail to visit every sub-cube." obviously you are not able to say so. Here's why: for $a_1,a_2$ you can pick any 2 numbers, let say 2 and 3. Each of the lines lay in one of the hyper-planes $3x_1-2x_2=0$, $3x_1-2(x_2-1)=0$, $3(x_1-1)-2(x_2-1)=0$, $3(x_1-1)-2(x_2-2)=0$

enter image description here

Those hyper-planes themselves don't visit each of the sub-cubes so neither the lines. Since you can pick for others $a_i$ any of numbers there are infinitely many such vectors

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. But I'm trying to eliminate most (hopefully all but finitely many) vectors. This is a "mini-max" problem. I'm looking for the largest minimum, so if I can show that most vectors have a small minimum, that's a huge step in the right direction. $\endgroup$ – B. Goddard Dec 3 '16 at 13:10

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.