Thread by @gro_tsen

So, here's a good approximation of a regular pentagon on a square lattice (to save you the bother of counting, the vertex positions are, up to translation: (0, 55), (−29, 34), (−18, 0), (18, 0), (29, 34)). How did I find it? 🧵⤵️ •1/18

Easy, you say: just pick any regular pentagon in the plane, and replace each one of its vertices by the closest lattice point! Well… yes, but that will give a very shitty approximation. To be honest, I didn't bother to compute how shitty, … •2/18

… but if you don't use the freedom to choose the size and orientation of your near-regular pentagon arbitrarily in the lattice, you won't do a good job (much like if you try to approximate ξ by rational p/q, you shouldn't just pick q arbitrarily and take p close to qξ). •3/18

What are we trying to do here? Find four size two vectors v₀,v₁,v₂,v₃ (the sides) with (smallish) integer coordinates such that v₁≈R·v₀, v₂≈R²·v₀, v₃≈R³·v₀ where R is rotation by 2π/5. The vertices will then be 0, v₀, v₀+v₁, v₀+v₁+v₂ and v₀+v₁+v₂+v₃. •4/18

(That's up to translation, of course: we don't care where the origin is. This is why I'm using the side vectors as unknowns, not the vertex positions, so as to kill one degree of freedom that's just irrelevant.) •5/18

A more sophisticated way of saying this (not too relevant for this thread, but still worth noting) is, if we replace v₀,v₁,v₂,v₃ by the corresponding complex numbers, which lie in ℤ[i], and R = exp(2iπ/5), we're trying to have v₁/v₀≈R, v₂/v₀≈R², v₃/v₀≈R³, … •6/18

… so we're trying to perform simultaneous Diophantine approximation of the three numbers (R,R²,R³) by ratios (v₁/v₀, v₂/v₀, v₃/v₀) of Gaussian integers with the SAME denominator: now simultaneous Diophantine approximation is hard, … •7/18

… even over the ordinary integers (and it's not made easier by working over the Gaussian integers), there's nothing miraculous like the Euclidean algorithm here, for which I refer to my previous thread (🔽). •8/18

https://twitter.com/gro_tsen/status/1493562259771117571

So instead, let me reformulate the problem as follows: consider the linear map T: ℝ⁸→ℝ⁸ (written as four pairs) which takes (v₀,v₁,v₂,v₃) to (Rv₀−v₁, R²v₀−v₂, R³v₀−v₃, c·v₀) where c is some to-be-decided (smallish) tuning parameter. •9/18

Our problem now becomes to find v=(v₀,v₁,v₂,v₃) in ℤ⁸ nonzero such that T(v) is small in ℝ⁸: the smallness of the first 3×2 coordinates means that v₁≈R·v₀, v₂≈R²·v₀, v₃≈R³·v₀, and the smallness of the last 1×2 means that v₀ is small(ish). •10/18

(So the tuning parameter c acts as a tradeoff between how hard we try to make v₀ small, i.e., our pentagon have small side coordinates, and the approximation good. The smaller c is, the more we care about the approximation quality, at the expense of size.) •11/18

What we are trying to do, now, is find a small nonzero vector in T(ℤ⁸). Now T(ℤ⁸) is a Euclidean lattice, and we know a base for it (namely the image by T of the standard basis of ℤ⁸), but finding the shortest nonzero vector in a Euclidean lattice is HARD … •12/18

… (“hard” as in “cryptographically hard”, in fact variants of this problem are used in various post-quantum cryptographic schemes). However, here, we don't care about the very shortest vector, we just care about finding some short vector. •13/18

Fortunately, there's an incredibly useful efficient (as in “polynomial”) algorithm to find reasonably short vectors in lattices (actually it does much more, it finds a reasonably good basis, but here we just care about a short vector): “LLL”. en.wikipedia.org/wiki/Lenstra%E… •14/18

Essentially, LLL takes a Euclidean lattice (here, T(ℤ⁸); actually it just cares about the Gram matrix Tᵗ·T of the lattice), and returns an invertible integral matrix U such that T·U is “close to being orthogonal”: its columns are the good basis of the lattice, … •15/18

… the first column of T·U is a shortish vector in the lattice, so here, the first column of the matrix U returned by LLL will be (v₀,v₁,v₂,v₃)∈ℤ⁸ we sought. •16/18

So, putting this together, here's the Sage code I used to find the pentagon shown above (note: what I called “T” in the above thread is called `m` in this code): gist.github.com/Gro-Tsen/b3e79… •17/18

Note: the answer I got (for weight c=1/200) happened to have a side aligned with an axis, I thought this was nice, but it's not necessarily the case, as this other example shows (whose vertices are (2,2), (0, 13), (10, 18), (18, 10), (13, 0)). •18/18