17
$\begingroup$

I was playing around with this demo of Project Euler Problem 208 which allows you to take steps which are "left" or "right" arcs of $1/5$ of a unit circle.

Here's an example walk, which starts at the blue dot pointing vertically up, and which consists of steps

RLLLRLLLRRLLLRLLLRRLRLLLR

example walk

Question

Which points in $\mathbb R^2$ can be reached in a finite number of steps, starting at the origin and pointing in the positive $y$-direction. Is this set of points dense in $\mathbb R^2$? If not, what's the greatest number of points that can land in $[0,1] \times [0,1] \subset \mathbb R^2$?

$\endgroup$
9
  • 2
    $\begingroup$ I would expect the points to be dense but it be a bit of work to prove. One way is to find sequences of moves that end with you facing the same direction but move the point in several directions. If the distances moved are not rational multiples of each other you can combine those movements to get as close as wanted to any point. RL and LR leave you heading in the same direction as at the start. You can compute the displacement they create, but they will be the same vertically and negatives horizontally. Now add RRLL and LLRR to the mix. You need $\endgroup$ Aug 22, 2019 at 23:02
  • $\begingroup$ a combination that moves you downward, but that shouldn't be hard to find. I would think something like RRRLRLRLRLRLLL would work, the first three to make (about a) U turn, the middle RLs to move in that direction, and the last three to reorient upward. $\endgroup$ Aug 22, 2019 at 23:05
  • $\begingroup$ This is a really interesting question. I might end up offering a bounty here $\endgroup$
    – clathratus
    Aug 23, 2019 at 0:37
  • 1
    $\begingroup$ I think one could reformulate this question so it is closely linked with the projective definition of the Penrose pattern: Take the standard Z^5 grid in the 5-dimensional vector space. One can put a 2-dimensional subspace E in such a way, that the 5 base vectors project to it pointing to the corners of a regular pentagon. Then your question should be equivalent to the question, If the projection of Z^5 to E is dense, right? I think this has been proven due to E having an irrational angle to the base vectors. $\endgroup$ Aug 24, 2019 at 15:02
  • 1
    $\begingroup$ Related:Rolling a random walk on a sphere: "The surface will be filled for every $\delta$ except $\pi/2$ and $\pi$." $\endgroup$ Aug 25, 2019 at 1:48

3 Answers 3

12
$\begingroup$

Yes, the set of points attainable by these paths is dense in $\mathbb{R}^2$. Pardon the lack of polish in this answer; I don't have a 'real' math background, so I'm expressing my ideas here using the language most intuitive to me.

We can think of any path as a linear combination of five 'moves,' which w.l.o.g. are given by the vectors $v_n = (\cos\frac{2\pi n}{5}, \sin \frac{2\pi n}{5})$. Paths cannot be arbitrary integer combinations of these vectors, since there are only two moves available after each step. We can, however, devise the following scheme to obtain arbitrary integer combinations of the vectors $2v_n$. Consider the following paths (I've written out the linear combination long form to show the order that the steps must be taken in each path):

\begin{align*} p_1^a &= 2av_1\\ p_2^b &= v_1 + 2bv_2 + v_1\\ p_3^c &= v_1 + v_2 + 2cv_3 + v_2 + v_1\\ p_4^d &= v_1 + v_2 + v_3 + 2dv_4 + v_3 + v_2 + v_1\\ p_5^e &= 2ev_5 \end{align*}

Graphically, these look something like this: $p_1^2$, $p_2^2$, $p_3^2$, $p_4^2$, $p_5^2$.

These paths are composable with each other, so we can take them in arbitrary (positive) integer combinations. Consider a point of the form $x = \sum_{i = 1}^5 p_i^{a_i}$. Writing this out in terms of our original moves $v_i$, we obtain \begin{align*} x &= p_1^a + p_2^b + p_3^c + p_4^d + p_5^e\\ &= (6 + 2a)v_1 + (4 + 2b)v_2 + (2 + 2c)v_3 + 2dv_4 + 2ev_5 \end{align*} We will ignore the constant offset $6v_1 + 4v_2 + 2v_3$. Using the paths $p_i^a$ alone, we can thus reach an arbitrary (nonnegative) integer combination of the vectors $\{2v_i\}$.

Now note that $\sum_{i = 1}^5 2v_i = 0$, so it follows that the vectors $2v_i$ and $\sum_{j \neq i} 2v_j$ are additive inverses. Thus the set of nonnegative integer combinations of the vectors $2v_i$ is actually equal to the set of arbitrary integer combinations of the vectors $2v_i$.

Digging around MathSE, I found this answer that asserts, based on Kronecker's theorem, that if three vectors have components that are all linearly independent over the rationals, then the set of their integer combinations is dense in the unit square (and by extension the plane). $2v_1$, $2v_2$ and $2v_3$ satisfy this hypothesis, so the claim should follow.

$\endgroup$
2
  • 1
    $\begingroup$ Pretty damn good for someone without a math background! (+1) $\endgroup$
    – clathratus
    Sep 6, 2019 at 4:04
  • 1
    $\begingroup$ Well, I'm a physics student, so I wouldn't say I have 'no' math background– just not a 'real' one. $\endgroup$
    – Panopticon
    Sep 6, 2019 at 18:08
9
$\begingroup$

Not an answer, but just an opportunity to mention that the behavior of the "Tangle Toy," which comes in quarter-circles,


         
          Image from FatBrainToys.
has been studied (but not addressing your question):

Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Quanquan Liu, Ron Taylor, and Ryuhei Uehara, “Tangled Tangles”, in The Mathematics of Various Entertaining Subjects (MOVES 2015), volume 2, 2017, pages 141–152, Princeton University Press. Authors' link.


         
          Fig.7: Tangle toy configurations.


To address @Narasimham's question, this paper

Tatu, Aditya. "Tangled Splines." arXiv:1610.03129. 2016-18.

says that the curvature $\kappa(t) =\pm 1$ outside of the knot points, and that torsion $\tau(t)$ is zero, again excluding knot points.

$\endgroup$
4
  • 1
    $\begingroup$ Interesting. Are curvature and torsion constant? $\endgroup$
    – Narasimham
    Aug 22, 2019 at 23:55
  • $\begingroup$ Curvature: yes. Torsion:no. $\endgroup$ Aug 23, 2019 at 7:45
  • $\begingroup$ @IvanNeretin: The cited paper says, "Since each link lies in the plane spanned by Vi and Vi+1, for each t ∈ (ti, ti+1), the torsion τ is zero." I have not tried to verify this, but you seem to be contradicting their claim? $\endgroup$ Aug 23, 2019 at 21:50
  • 1
    $\begingroup$ All right, the torsion is zero within each link and infinite at the joints. $\endgroup$ Aug 23, 2019 at 22:01
3
$\begingroup$

Here's a formulation that may help with calculation a bit: define a 'position' as $\langle x, y, \theta\rangle$, where $\theta$ is the angle being made with the $y$ axis; in other words, the starting position is $\langle0, 0, 0\rangle$. Then if you draw the geometry out (which I will try and do once I get onto a machine with better drawing tools) from $\langle x, y, 0\rangle$ the available moves are to $\langle x+(1-\cos(2\pi/5)), y+\sin(2\pi/5), \pi/10\rangle$ and $\langle x-(1-\cos(2\pi/5)), y+\sin(2\pi/5), -\pi/10\rangle$. Since the local frame at angle $\theta$ has its $x$ axis in the direction $\langle \cos\theta, \sin\theta\rangle$ and its $y$ axis in the direction $\langle -\sin\theta, \cos\theta\rangle$ (modulo possible sign errors) then this means that from $\langle x, y, \theta\rangle$ the available moves are to $\langle x+\cos\theta(1-\cos(2\pi/5))-\sin\theta\sin(2\pi/5), y+\cos\theta\sin(2\pi/5)+\sin\theta(1-\cos(2\pi/5)), \theta+\pi/10\rangle$ and to $\langle x-\cos\theta(1-\cos(2\pi/5))-\sin\theta\sin(2\pi/5), y+\cos\theta\sin(2\pi/5)-\sin\theta(1-\cos(2\pi/5)), \theta-\pi/10\rangle$. Since the cosine and sine of $2\pi/5$ and $\pi/10$ have nice clean expressions in terms of $\sqrt{5}$, you should be able to get explicit expressions in terms of $\sqrt{5}$ for the coordinates after making multiple moves as in Ross Millikan's comment, and then use some usual irrationality-of-square-roots arguments to show density. (But of course, note that there's a little subtlety to these arguments, because the same statement with sixth-turns around the circle are false!)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .