0
$\begingroup$

Consider a lattice $\mathcal{L} = \mathbb{Z}v_1 \oplus \ldots \oplus \mathbb{Z}v_l$ in $\mathbb{R}^n$ and let $S_0$ be the set of edges of the fundamental unit of $\mathcal{L}$. We call a region $X$ lattice path connected iff for every two lattice points $P$ and $Q$ there exists a path of lattice points $P = M_1, M_2, \ldots, M_{t - 1}, M_t = Q$ with $M_i = M_{i-1} + u_i$ and $u_i \in S_0$ and $M_i \in X$.

Let $P \subset \langle v_1, \ldots, v_l \rangle$ be a convex $k$ dimensional polytope. Suppose the supporting linear space of $P$ has spanning set $\mathbf{S}$ which is a subset of $S_0$ and moreover every codimension $1$ face has a spanning set which is a subset of $\mathbf{S}$.

Is it true that $P$ is lattice path connected ? This seems very intuitive as one would just follows the direction of the codimension $1$ faces to connect the two points.

Still, I'm curious to see if such a result is known.

Here are two examples in $\mathbb{R}^2$.

1) Take $\mathcal{L}$ to be the standard lattice. Then the polytopes in question are just horizontal segments, vertical segments and rectangles which are trivially $\mathcal{L}$ - connected.

2) Take $\mathcal{L}$ to be the triangular matrix whose fundamental unit is the equilateral triangle with vertices $(0,0), (1,0), e^{\frac{i\pi}{3}}$. Here there are more classes of polytopes whose edges are parallel to the edges of the fundamental unit. Even so, a case by case analysis shows that the result still holds true.

EDITED. (formalism of lattices and fundamental units)

I'll try a formal definition. First let's consider a lattice $\mathcal{L}$ just a set of points given by sum direct sum $\mathbb{Z}v_1 \oplus \ldots \oplus \mathbb{Z}v_n \subset \mathbb{R}^n$. So far $\mathcal{L}$ is just a set of points. There are "no directions" attached to it. There is no notion of "adjacency". There is no "repeating pattern".

One could of course define such notions by just using the $v_1, \ldots, v_n$ coordinates. Then the repeating pattern would be the convex polytope with vertices in $0$, the $v_i$s, the $v_i + v_j$s and so on. But then morally, one simply recovers the "standard" lattice $\mathbb{Z}^n$ with the "standard" directions.

However there are of courses lattices that have the same set of points $\mathcal{L}$ but the directions and repeating pattern distinct. How do we morally define them as "different lattices".

Well $v_1, \ldots, v_n$ are just lattice points that happen to form a basis for $\mathcal{L}$ but there are of courses other spanning sets of lattice points in $\mathcal{L}$.

A fundamental unit for $\mathcal{L}$ is a finite set of lattice points $\{u_1, \ldots, u_k\}$ of $\mathcal{L}$ that form a convex polytope $K$ with edges $k_1, \ldots, k_s$ such that $\mathcal{L} = \mathbb{Z}k_1 + \ldots + \mathbb{Z}k_s$.

So for me a lattice is really the initial data $\mathcal{L}, K$.

$\endgroup$
  • $\begingroup$ I am confused. How is this possible? Would you give some example on the plane? $\endgroup$ – Fedor Petrov Jan 26 '17 at 15:37
  • $\begingroup$ @FedorPetrov I made some corrections and provided a couple of examples. I am trying to prove some polytope is lattice path connected but I couldn't find any results in the literature so I'm trying to come up with all sorts of criterions when this might hold true. $\endgroup$ – Alex Jan 27 '17 at 11:22
  • 2
    $\begingroup$ What do you mean by a fundamental unit? I supposed this is a parallelepiped, not a triangle. $\endgroup$ – Fedor Petrov Jan 27 '17 at 12:01
  • 1
    $\begingroup$ Lattices are well defined concepts, and your "definitions" do not seem to match this. There also does not exist a "standard lattice" per se, nor can you define a lattice as a matrix. And if two lattices contain exactly the same sets of points, then they are the same lattice - you are just talking about different bases for the same lattice. $\endgroup$ – TMM Feb 1 '17 at 13:50
  • 1
    $\begingroup$ "However there are of courses lattices that have the same set of points L but the directions and repeating pattern distinct. How do we morally define them as "different lattices". - This in particular does not make sense - they are not different lattices. $\endgroup$ – TMM Feb 1 '17 at 13:52
1
$\begingroup$

(Edited Feb 3 to correct previous wrong example)

Let me try a simpler example than in my comments. Consider the lattice $\mathbb{Z}^2$ and the polygon $P$ with vertices $(0,0)$, $(1,-3)$, $(2,-3)$, $(3,1)$, $(2,4)$ and $(1,4)$. (This is the Minkowski sum of vectors $(1,-3)$, $(1,0)$ and $(1,4)$). And consider $P$ itself as a "fundamental unit" for the lattice.

The points $(1,-1)$ and $(2,-1)$ are in $P$ but cannot be connected to the rest of lattice points in $P$ using the edges of $P$. (They can be connected to one another, but not to the rest). The same holds for the points $(1,2)$ and $(2,2)$.

Update (Feb 4): this example is still wrong, but the one by Yoav Kallus in the comment below works.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ If I understand the question and your example, this is still not a counterexample to the OP's proposed conjecture: $(2,-1)$ is connected to $(1,2)$ by the vector $(-1,3)$ which is a side of $P$. But I think there is a simpler counterexample: Let $K$ be the Minkowski sum of the segments from the origin to the points $k_1=(1,1)$, $k_2=(1,-1)$ and $k_3=(500,501)$. Let $P$ be the Minkowski sum of only the first two, then $(1,0)\in P$ is not connected to the rest of $P$. $\endgroup$ – Yoav Kallus Feb 4 '17 at 2:46
  • $\begingroup$ @Yoav Kallus; You are right... second failed attempt on my side. And in fact your idea is conceptually much simpler. For a smaller (coordinate-wise) example, your $k_3$ can be changed to any vector with odd sum of coordinates and different from $(\pm 1,0)$ or $(0,\pm 1)$. (E.g, $k_3=(3,0)$ or $k_3=(2,1)$ work). $\endgroup$ – Francisco Santos Feb 4 '17 at 13:17
0
$\begingroup$

I think indeed the claim is true under some "weak" assumptions on the fundamental unit. For instance let $\langle u_i, x \rangle = b_i$ be the equations of the codimension $1$ faces of the fundamental unit with $1 \leq i \leq N$ where $N$ is the number of such faces. Assume that $u_i \in \mathbb{Z}^n$, $b\in \mathbb{Z}$, $\langle u_i, k_j\rangle \leq 1$ for any $1 \leq i \leq N$ and any $1 \leq j \leq s$. I'll give a plausibility argument.

Consider two points $X$ and $Y$ in $P$ and consider $M_X$ (resp. $M_Y$) the set of all lattice points in $P$ that have a lattice path to $X$ (resp. $Y$). If $X$ and $Y$ are not connected then $M_X \cap M_Y = \emptyset$. For every point $X'\in M_X$ and every point $Y'\in M_Y$ we have that there exists an integer combination (actually infinitely many)

\begin{align*} Y' = X' + a_1 k_1 + \ldots a_s k_s \hspace{2cm}(1)\end{align*} where $a_i \in \mathbb{Z}$ and the $k_i$ are the edges of the fundamental unit. Out of all the pairs $(X', Y') \in M_X \times M_Y$ and out of all combinations as in (1) choose one $(X_0, Y_0)$ for which $|a_1| + \ldots .. |a_s|$ is minimal.

LEMMA 1. Let $Z$ be an interior lattice point of $P$. Then for every $1 \leq i \leq s$, $Z + k_i$ is also a lattice point in $P$ (possibly on the boundary).

Now pick an index $i$ such that the integer combination (1) for the pair $(X_0, Y_0)$ has $a_i \neq 0$. If $a_i > 0$ set $X_1 = X_0 + k_i$ otherwise set $X_1 = X_0 - k_i$. By Lemma 1 $X_1$ is also in $P$.

Then the pair $(X_1, Y_0)$ contradicts the minimality of $(X_0, Y_0)$. Now such an argument connects $X$ and $Y$ possibly through the boundary. If we want connectivity to "respect" faces of $P$, in the sense that interior points are connected by paths lying completely in the interior, then what one can do, is create a scaled copy of $P$ inside $P$ that doesn't exclude any of the interior lattice points of $P$.

PROOF OF LEMMA 1. Assume there is an index $i$ (WLOG let $i$ = 1) such that $Z + k_1$ is not in $P$. Then the segment joining $Z$ and $Z + k_1$ intersects a codimension one face $F$ of $P$ in a point $Z_0$.

Let $S_F$ be the maximal subset of $\{k_1, \ldots, k_s\}$ with the property that all of its elements are parallel to $F$. Then $k_1 \not\in S_F$. Let $\langle u, x\rangle = b$ be the defining equation of $F$. Because $Z$ is in the interior of $P$, we have that $\langle u, Z \rangle < b$. Now $\langle u, Z + k_1 \rangle = \langle u, Z \rangle + \langle u, k_1 \rangle < b + 1$. Since everything is integer we get $\langle u, Z + k_1 \rangle \leq b$. But then it has to be the case that $P\ni Z_0 = Z + k_1$ thus finishing the proof.

I should mention that the hypothesis that the faces of $P$ have spanning sets made of edges of the fundamental unit is used for

(a) connectivity of faces of $P$

(b) connectivity of the interior of $P$ using only paths lying completely in this interior.

| cite | improve this answer | |
$\endgroup$

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.