The Setting
Take a self-avoiding walk in , a sequence of distinct Gaussian integers, and a forward segment of it whose steps have length at most . Its points form a set of Gaussian integers, and the question is how many distinct differences with such a set must have. The region the segment covers may be a thin strip of length about or a disc of radius about , and its size is measured by the area of a rectangle containing the segment.
The same comparison has a form for two finite walks from with steps at most , one ending at and one at : how large must a set of Gaussian integers be that contains every difference of a point of the first walk and a point of the second, against the area of the parallelogram spanned by and ? This is the setting of a discrete Sperner lemma for rectangles. Part (c) of Theorem 1, stated below, is its form for three points of one segment spanning a triangle.
Differences, Lattice Balls and Rectangles
For a finite set of Gaussian integers, the difference set is the finite set (1)✦ of Gaussian integers, and is its number of elements.
The point set of the segment of length of a sequence of Gaussian integers is the set of its first terms.✦
For a real number , the lattice ball of radius is the finite set of Gaussian integers at distance at most from in , and is its number of elements: (2)✦
The determinant of Gaussian integers and is the integer (3) its absolute value is the area of the parallelogram spanned by and , and it vanishes exactly when , and lie on a line.
An oriented rectangle of length and half-width is a subset of of the form (4) with and .
The Claim
Theorem 1. (a) Let be a real number and an integer, let be a self-avoiding walk in with for , and let . Then there are real numbers and with and an oriented rectangle of length and half-width containing such that (5)✦
(b) Let be a real number, integers and Gaussian integers with , and let and be finite walks in with steps at most , from to and from to . If is a finite set of Gaussian integers containing for all and , then (6)✦
(c) Let be a real number and an integer, let be a sequence of Gaussian integers with for , and let . If and , then (7)✦
In the paper, the result reads: if is the set of points of a segment of steps of the walk, its diameter and the larger of and the maximal distance of a point of from a diameter line, then satisfies and , with absolute and depending only on .
Part (a) takes for and the length and half-width of a rectangle containing the segment, in place of the diameter and the distance from a diameter line, and gives and .
What Is Checked
The claim is stated over sequences of Gaussian integers with distances taken in , the point set of a segment, the difference set (1), the lattice ball of radius with its elements (2), the determinant (3) and the oriented rectangles (4).