STEINHAUS SETS AND JACKSON SETS

SU GAO, ARNOLD W. MILLER, AND WILLIAM A. R. WEISS

Abstract. We prove that there does not exist a subset of the plane S that meets every isometric copy of the vertices of the unit square in exactly one point. We give a complete characterization of all three point subsets F of the reals such that there does not exists a set of reals S which meets every isometric copy of F in exactly one point.

1. Introduction

A finite set X ⊆ ℝ^{2} is Jackson iff for every S ⊆ ℝ^{2} there exists an isometric copy Y of X such that |Y ∩ S| ≠ 1.

Question 1.1 (Jackson). Is every finite set X ⊆ ℝ^{2} of two or more points Jackson?

This question is motivated by the solution of the Steinhaus problem due to Jackson and Mauldin [4, 5, 6]. They showed that there exists S ⊆ ℝ^{2} such that S contains exactly one point from each isometric copy of ℤ^{2}, i.e., there is a Steinhaus set for ℤ^{2}. Analogous results were obtained by Komjath [8, 9] and Schmerl [10] for ℤ, ℚ, and ℚ^{2}.

Note that a set is Jackson iff the Steinhaus problem for it has a negative solution. As far as we know the answer to this question is yes, but we have only partial results. We do not know if every four point set is Jackson.

In fact we would like to consider a more general version of the problem as the dimension of the ambient space varies. We will use the following terminology.

Definition 1.2. Let n ≥ 1 and X ⊆ ℝ^{n}. A set S ⊆ ℝ^{n} is a Steinhaus set for X in ℝ^{n} if for every isometric copy Y of X in ℝ^{n}, |Y ∩ S| = 1. X is a Jackson set in ℝ^{n} if there is no Steinhaus set for X in ℝ^{n}.

1991 Mathematics Subject Classification. 52C20, 05C12, 11H06.

Key words and phrases. isometries of the plane, tilings, periodic subsets of the reals, distance one graph, unit square, chromatic number, reflection argument, lattices.

In section 2 we focus on finite sets in ℝ^{1} and in section 3 on finite sets in ℝ^{2}.

The empty set is vacuously Jackson. A singleton is never Jackson. If X = {x_{0}, x_{1}} ⊆ ℝ and d = |x_{0} − x_{1}| > 0, then the set

S = ⋃_{n∈ℤ}[2nd, (2n + 1)d)

is easily seen to be a Steinhaus set for X in ℝ. Moreover in this case the Steinhaus set is not unique. In contrast, if X = {x_{0}, x_{1}} ⊆ ℝ^{n} for any n ≥ 2, then the following argument shows that X is Jackson. Suppose S is any Steinhaus set for X in ℝ^{n} and suppose y_{0} is any element of S. We still use d(x_{0}, x_{1}) to denote the distance between x_{0} and x_{1}. Consider any line l through y_{0} in ℝ^{n} and let y_{1} and y_{2} be points on l so that d(y_{0}, y_{1}) = d(y_{1}, y_{2}) = d and d(y_{0}, y_{1}) = 2d. Since y_{0} ∈ S and {y_{0}, y_{1}} is an isometric copy of X, we have that y_{1} ∉ S. But {y_{1}, y_{2}} is also an isometric copy of X, therefore y_{2} ∈ S. Thus we have shown that any point of distance 2d from y_{0} must be in S. In other words, the sphere of radius 2d centered at y_{0} is a subset of S. However, this is a contradiction since it is easy to find two points on this sphere with distance d between them. A similar argument shows that any three point set in ℝ^{n} for n ≥ 2 is Jackson (see Proposition 3.1.)

This reflection argument is used to derive contradictions in most of our proofs.

For the rest of the paper we may assume |X| ≥ 3.

It is easy to see that if a set X ⊆ ℝ^{n} is Jackson in ℝ^{n} then as a subset of ℝ^{n+1}, X is also Jackson in ℝ^{n+1}. The converse is not true.

Another basic point is that if X and X′ (in some ℝ^{n}) are similar, then X is Jackson in ℝ^{n} iff X′ is Jackson in ℝ^{n}. This is because we can apply the similarity transformation to a Steinhaus set for X to get a Steinhaus set for X′ (and vice versa).

We end this introduction by connecting our problem with the coloring number of a distance graph. For D a set of positive reals define the graph G(ℝ^{n}, D) by letting ℝ^{n} be the vertices and connecting p, q by an edge iff d(p, q) ∈ D. The chromatic number of a graph G is the smallest n such that the vertices of G can be partitioned into n sets such that in each set no two vertices are adjacent.

Given any finite set F ⊆ ℝ define

D(F) = {d(p, q) : p, q ∈ F, p ≠ q}

Proposition 1.3. For F ⊆ ℝ^{n} finite the following are equivalent: (1) There is a Steinhaus set S ⊆ ℝ^{n} for F.

(2) The chromatic number of G(ℝ^{n}, D(F)) ≤ |F |.

Proof. Suppose S is a Steinhaus set for F. Consider

{p + S : p ∈ F }.

Note that this is a partition of ℝ^{n} into Steinhaus sets for F. To see that it covers ℝ^{n} note that for any q ∈ ℝ^{n} that (q − F) ∩ S ≠ ∅ hence there exists p ∈ F with q − p ∈ S and so q ∈ p + S. The sets are pairwise disjoint since otherwise there would be distinct p_{1}, p_{2} ∈ F and s_{1}, s_{2} ∈ S with p_{1} + s_{1} = p_{2} + s_{2} and so p_{1} − p_{2} = s_{2} − s_{1} and so d(p_{1}, p_{2}) = d(s_{1}, s_{2}). But then S would meet an isometric copy of F in at least two points.

Hence the chromatic number of G is less than or equal to |F |.

Conversely, suppose that the chromatic number of G is |F |. (It cannot be smaller since the elements of F must receive different colors.) Let

ℝ^{n} = ⋃_{i<|F |} S_{i}

Fix an isometric copy of F say F′. Then each S_{i} must meet F′ in at most one point. But since there are exactly |F | of the S_{i} each must meet F′ in exactly one point. □

A well-known open problem (see Klee and Wagon [7]) is to determine the chromatic number of the distance one graph in the plane. In our terminology this graph would be G = G(ℝ^{2}, {1}), i.e., two points in the plane are adjacent iff the distance between them is exactly one. It is known that the chromatic number of G is between 4 and 7.

Proposition 1.4. Suppose that the chromatic number of the distance one graph G is strictly greater than 4. Then every four point subset of ℝ^{2} is Jackson.

Proof. By considering a similar copy of F we may assume there are two points of F which are exactly one unit apart. Hence by the above proposition a Steinhaus set for F would yield a coloring for G with four colors. □

A similar result holds if the chromatic number is greater than 5 or greater than 6. Falconer [3] has shown that if the plane is covered by four measurable sets, then one of the sets contains two points exactly unit one apart. Hence, no four point subset of the plane has a measurable Steinhaus set.

2. Steinhaus sets and Jackson sets on the Line

All Steinhaus sets and Jackson sets in this section will be subsets of ℝ.

We begin by giving a complete classification of 3-point Jackson sets on the line. This is done in two cases. By our similarity argument we may assume that the three point set has the form {0, α, 1} where 0 < α < 1. We begin by considering the case where α is a rational number. In this case (again by similarity) we may assume that the elements of our set are integers. Obviously, if F is a finite set of integers, then F has a Steinhaus set in ℝ iff F has a Steinhaus set S ⊆ ℤ, i.e., S meets every isometric copy of F in ℤ.

Proposition 2.1. Let F = \{0, α, 1\} where α = \frac{n}{m} and n and m are relatively prime. Then the following are equivalent:

(i) There exists a Steinhaus set S for F in ℝ.

(ii) {n mod 3, m mod 3} = {1, 2}.

(iii) S = {3k : k ∈ ℤ} is a Steinhaus set for {0, n, m} in ℤ.

Proof. (ii)⇒(iii): It is easy to see that every isometric copy of {0, n, m} in ℤ contains exactly one element u such that u = 0 mod 3.

(iii)⇒(i): Let

S^{∗} = \{u + \frac{k}{m} : k ∈ S, 0 ≤ u < 1\}.

Then since S meets every isometric copy of {0, n, m} in ℤ in exactly one point, then S^{∗} meets every isometric copy of F in ℝ in exactly one point.

(i)⇒(ii): There exists a Steinhaus set S ⊆ ℤ for {0, n, m}. And since the translation of any Steinhaus set is Steinhaus we may assume 0 ∈ S. Note that for any set S its possible periods

{p ∈ ℝ : ∀x ∈ ℝ x ∈ S iff p + x ∈ S}

is a subgroup of the additive group of ℝ. The gaps in the set {0, n, m} are a = n and b = m − n. So by the usual reflection argument (see figure 1) both a + 2b and 2a + b are periods of S. Let

H = {k(2a + b) + l(a + 2b) : k, l ∈ ℤ}.

Since 0 ∈ S we have that H ⊆ S. Let d = gcd(2a + b, a + 2b) and note that H = {kd : k ∈ ℤ}. Since 0 ∈ S we have that a ∉ S and b ∉ S and so d does not divide either a or b.

Note that

a − b = (2a + b) − (a + 2b),
3a = 2(2a + b) − (a + 2b), and 3b = 2(a + 2b) − (2a + b),

so we have that d|(a − b), d|3a and d|3b. Since d does not divide a, we can write d = 3c where c|a. Similarly, we have c|b. Thus c = 1 =

[figure: b; a; b; x; x + a + 2b; a; b; a; x; x + 2a + b]

Figure 1. Reflection

gcd(a, b) and d = 3. Now since d|(a − b) we have

a ≡ b (mod 3).

Hence n ≡ m − n (mod 3) but since n and m are relatively prime one must be 1 mod 3 and the other 2 mod 3.

□

Another proof of this proposition can be given by using a result of Zhu [12] and the method of Proposition 1.3. Zhu determines the chromatic number of all distance graphs G(ℤ, D) where |D| = 3. Our result corresponds to the special case that D = {n, m, m − n}

Note that in Proposition 2.1 if there is a Steinhaus set for \{0, \frac{m}{n}, 1\}, there is one which is the union of a closed set and an open set.

Proposition 2.2. Let 0 < α < 1 be irrational. Then there is a Steinhaus set for F = {0, α, 1}. However, there is no Steinhaus set for F which is either Lebesgue measurable or has the Baire property.

Proof. Let S be a Steinhaus set for F. The gap lengths in F are a = α and b = 1 − α and so by the usual reflection argument (see figure 1) both 2a + b = 1 + α and a + 2b = 2 − α are periods of S. Let

H = {m(1 + α) + n(2 − α) : m, n ∈ ℤ}.

Then for every h ∈ H and x ∈ ℝ we have that

x + h ∈ S iff x ∈ S.

Now consider the quotient group ℝ/H. For any r ∈ ℝ, we denote by ⟨r⟩ the coset r + H. We claim that G = {⟨0⟩, ⟨α⟩, ⟨1⟩} is a subgroup of ℝ/H. For this note that 1 + α ∈ H gives that ⟨1⟩ + ⟨α⟩ = ⟨0⟩, so ⟨α⟩ = −⟨1⟩. On the other hand, 2−α ∈ H implies that ⟨2⟩−⟨α⟩ = ⟨0⟩, thus ⟨α⟩ = 2⟨1⟩. Putting these together we have that 2⟨1⟩ = ⟨α⟩ and 3⟨1⟩ = ⟨0⟩. Thus the G is a cyclic group of order at most 3. To see that G has order exactly 3, we need only argue that ⟨1⟩ ≠ ⟨0⟩, i.e., 1 ∉ H. But this is obvious since otherwise α would be rational.

We are now ready to define a Steinhaus set for F. First choose a transversal for the cosets of G in ℝ/H, i.e., a set S̃ ⊆ ℝ/H such that S̃ meets each coset of G at exactly one point. Then let S = ⋃ S̃, i.e., the union of all elements of S̃. We check that S is a Steinhaus set as required. For this let x ∈ ℝ. First consider the 3-point set {x, x + α, x + 1}. Since the set {⟨x⟩, ⟨x⟩ + ⟨α⟩, ⟨x⟩ + ⟨1⟩} = ⟨x⟩ + G is a coset of G in ℝ/H, there are exactly one element of ⟨x⟩ + G which is in S̃ and therefore exactly one of x, x + α and x + 1 which is in S. Next consider the 3-point set {x, x − α, x − 1}. Using the facts that ⟨x⟩ − ⟨α⟩ = ⟨x⟩ + ⟨1⟩ and ⟨x⟩ − ⟨1⟩ = ⟨x⟩ + ⟨α⟩ we can argue similarly that exactly one of x, x − α and x − 1 is in S.

Next we show that no Steinhaus set for F can be measurable or have the property of Baire. We claim that H is dense in ℝ. To see this, let β = (1 + α)/(2 − α). Since α = (1 + β)/(2 − β) we have that β is also irrational. Let

K = {n + mβ : n, m ∈ ℤ}.

We claim that K cannot be a discrete subgroup of the reals. If it were then there would be some ϵ > 0 such that for every x, y ∈ K if |x − y| < ϵ then x = y. So if it were discrete there would have to be minimal positive element δ ∈ K. It is easy to see that

K = {nδ : n ∈ ℤ}

since otherwise if x ∈ K and n ∈ ℤ with nδ < x < (n + 1)δ would give us 0 < x − nδ < δ. But since 1 ∈ K we have δ = \frac{1}{n} for some positive integer n. Since β ∈ K we would get that β is a rational. Hence K is dense and since

H = {(2 − α)x : x ∈ K}

we also have that H is dense.

Since H +S = S and H is dense, it follows that if S has the property of Baire it must be either meager or comeager. This is because if S is comeager in an open interval I then h + S is comeager in h + I. But h + S = S for any h ∈ H and since H is dense, S would have to comeager in ℝ. Similarly, if S is measurable then it is either measure zero or the compliment of a measure zero set.

But S, α + S, 1 + S is a partition of the reals (see the proof of Proposition 1.3). Hence it cannot be either meager or comeager (or measure zero or comeasure zero).

□

As the proofs above show, the length of the gaps between successive elements of F are important.

It will sometimes be convenient to use the following gap terminology.

Definition 2.3. Let n ≥ 2 and a_{1}, …, a_{n} be positive real numbers. A finite set X of n + 1 elements has type (a_{1}, …, a_{n}) if X is similar to the set

A(a_{1}, …, a_{n}) = {0, a_{1}, a_{1} + a_{2}, …, a_{1} + a_{2} + ⋯ + a_{n}}.

As remarked before, if X has type (a_{1}, …, a_{n}), then Steinhaus sets for X (if they exist) are in one-one correspondence with Steinhaus sets for the set A(a_{1}, …, a_{n}) above. For simplicity we will call the latter sets Steinhaus sets for (a_{1}, …, a_{n}).

Next we show that Proposition 2.2 can be generalized to arbitrary sequences (r_{1}, …, r_{n}) with positive real numbers r_{1}, …, r_{n} linearly independent over ℚ. Note that the linear independence can be equivalently formulated as follows: for any k_{1}, …, k_{n} ∈ ℤ, if k_{1}r_{1} + ⋯ + k_{n}r_{n} = 0 then k_{1} = ⋯ = k_{n} = 0.

Proposition 2.4. Let (r_{1}, …, r_{n}) be a sequence of positive real numbers linearly independent over ℚ. Then there is a Steinhaus set for (r_{1}, …, r_{n}).

Proof. Let H be the additive subgroup of ℝ generated by the elements:

(n + 1)r_{1}, r_{2} − r_{1}, r_{3} − r_{1}, …, r_{n} − r_{1}.

Note that these generators are also linearly independent over ℚ.

Consider the quotient group ℝ/H and let ⟨r⟩ denote the coset r + H for r ∈ ℝ. Then we note that ⟨r_{1}⟩ = ⟨r_{2}⟩ = ⋯ = ⟨r_{n}⟩ and (n+1)⟨r_{1}⟩ = ⟨0⟩. Let G be the cyclic group in ℝ/H generated by ⟨r_{1}⟩. We claim that G has order n + 1. To see this, we show that for any k ∈ ℤ, kr_{1} ∈ H iff (n + 1)|k. Let k_{1}, …, k_{n} ∈ ℤ. Then

kr_{1} = k_{1}(n + 1)r_{1} + k_{2}(r_{2} − r_{1}) + ⋯ + k_{n}(r_{n} − r_{1})
⇔ (k_{1}(n + 1) − k − k_{2} − ⋯ − k_{n})r_{1} + k_{2}r_{2} + ⋯ + k_{n}r_{n} = 0
⇔ k_{1}(n + 1) − k − k_{2} − ⋯ − k_{n} = k_{2} = ⋯ = k_{n} = 0
⇒ k_{1}(n + 1) = k.

We construct S as before. First let S̃ be a transversal for the cosets of G in ℝ/H. Then let S = ⋃ S̃. Then S is a required Steinhaus set by a similar argument as before. □

The following example shows that there are Jackson sets of type (r_{1}, …, r_{n}) where at least one pair of numbers have an irrational ratio.

Example 2.5. For any real number r > 0, the set A(1, r, 2) is Jackson.

Proof. Assume S is a Steinhaus set for A(1, r, 2) = {0, 1, 1 + r, 3 + r} and 0 ∈ S. Then −1, 1, 1+r, 2+r are each not in S since their distances to 0 are forbidden. i.e, in D(A(1, r, 2)). But the set {−1, 1, 1 + r, 2 + r} is an isometric copy of {0, 1, 1 + r, 3 + r}, (i.e. reflect across the interval of length r). Thus it should meet S in exactly one point, a contradiction. □

In what follows we will give various other examples of 4-point Jackson sets. We have ad hoc arguments for 4-point sets of more types than covered here. However, a complete classification for 4-point Jackson sets is not known.

For the remainder of this section we will only consider finite subsets of the integers ℤ and Steinhaus sets in ℤ.

Recall that a set S ⊆ ℝ is periodic if there is p > 0 such that for any x ∈ ℝ,

x ∈ S iff x + p ∈ S.

In this case p is called a period for S.

Proposition 2.6. Let F ⊆ ℤ be finite and let d be the diameter of F, i.e., d = max(F) − min(F). If F has a Steinhaus set, then F has a Steinhaus set with integer period p with 0 < p ≤ d2^{d}.

Proof. Let S be a Steinhaus set for F. For 0 ≤ k ≤ 2^{d}, define a function f_{k} : {0, …, d − 1} → {0, 1} by letting

f_{k}(t) = 1 iff ks + t ∈ S.

Since there are 2^{d} + 1 functions f_{k} but only 2^{d} many functions from {0, …, d − 1} to {0, 1}, there must be k_{1} < k_{2} such that f_{k_{1}} = f_{k_{2}}.

Let p = (k_{2} −k_{1})d and define a set S′ ⊆ ℤ to be periodic with period p such that S′ ∩ I = S ∩ I where I is the interval [k_{1}d, (k_{2} + 1)d). This is possible because S is the same on the first and last d-subintervals of I.

We check that S′ is a Steinhaus set for F. Let X be an isometric copy of F in ℤ. Let x_{0} be the smallest element of X and note that x_{0} + d is the largest element of X. Choose n ∈ ℤ so that

(n − 1)p + x_{0} < k_{1}d ≤ np + x_{0}.

Note that np + x_{0} < k_{2}d. Hence, np + X ⊆ I. Since S and S′ agree on I it must be that S′ meets np + X in exactly one point. Since S′ has period p it meets X in exactly one point.

□

A proof of this proposition can also be given by noting that periodic colorings give a periodic Steinhaus set (proof of Proposition 1.3) and using the proof of Theorem 2 of Eggleton, Erdos, and Skilton [2]. Their proof works for any finite distance set D ⊆ ℤ although they assume D contains only primes.

Let J denote the set of all finite sequences of positive integers F such that F is Jackson.

Theorem 2.7. The set J is computable.

Proof. It is clear from the last proof that F with diameter d has a Steinhaus set iff there exists S ⊆ {0, 1, …, d2^{d}} which meets every isometric copy of F inside {0, 1, …, d2^{d}} in exactly one point. But this is clearly computable. □

However, the following question seems to be open.

Question 2.8. Is J computable in polynomial time?

Regarding periodic Steinhaus sets we have the following useful fact.

Proposition 2.9. Let F be a finite set of positive integers. If S is a periodic Steinhaus set for F, with an integer period p, then p is a multiple of n = |F |. In fact, p = mn where m = |S ∩ {0, 1, …, p − 1}|.

Proof. Let F = {b_{1}, b_{2}, …, b_{n}}. Consider the p×n-matrix (c_{ij}) defined as follows: for i = 0, …, p − 1 and j = 1, …, n, let

c_{ij} = \{ \begin{matrix}1 & if i + b_{j} ∈ S \\ 0 & otherwise \end{matrix}

Note that for each i < p there is exactly one j such that c_{ij} = 1 because |(i + F) ∩ S| = 1. Hence the total number of ones in the matrix C is p.

On the other hand for each fixed j = 1, …, n

|{0 ≤ i < p : i + b_{j} ∈ S}| = |{0 ≤ i < p : i ∈ S}| = m

since p is a period of S. Hence the total number of ones in the matrix C is mn.

Therefor p = mn.

□

The proposition has many applications. One can get a taste of the flavor of these applications from the simple example below.

Example 2.10. Let a and b be positive integers such that a+b is odd. Then the set A(a, b, b) is Jackson.

Proof. Toward a contradiction assume S is a Steinhaus set for A(a, b, b). Note that by reflection 2a + 2b = a + b + b + a is a period for S. But since a + b is odd, 2a + 2b is not a multiple of 4, contradicting the preceding proposition. □

In the next few propositions we investigate when a Steinhaus set exists with a given period. We start with the simplest case.

Proposition 2.11. Let (a_{1}, …, a_{n}) be a sequence of positive integers. The following are equivalent:

(i) A Steinhaus set of period n + 1 exists for (a_{1}, …, a_{n}).

(ii) A(a_{1}, …, a_{n}) ≡ {0, …, n} (mod n + 1).

(iii) For any x ≠ y elements of A(a_{1}, …, a_{n}), x ≢ y (mod n + 1).

Proof. Clauses (ii) and (iii) are obviously equivalent since

|A(a_{1}, …, a_{n})| = |{0, …, n}| = n + 1

and thus a map (in this context the mod n + 1 map) between the two sets is onto iff it is one-one. To see that (i)⇒(iii), let S is a Steinhaus set of period n+1 for (a_{1}, …, a_{n}) and without loss of generality assume 0 ∈ S. Assume that there are distinct x and y from A(a_{1}, …, a_{n}) with x ≡ y (mod n + 1). Then y − x ∈ S by the periodicity of S. Now 0, y − x ∈ A(a_{1}, …, a_{n}) − x and hence A(a_{1}, …, a_{n}) − x, an isometric copy of A(a_{1}, …, a_{n}), meets S at two points, a contradiction.

To see that (ii)⇒(i), it suffices to note that the set

S = {k(n + 1) : k ∈ ℤ}

is a Steinhaus set for (a_{1}, …, a_{n}). S obviously has period n + 1. Let X ⊆ ℤ be any isometric copy of A(a_{1}, …, a_{n}). Then the mod n + 1 values of X are distinct. It follows that there is exactly one element of X in S. □

Example 2.12. There are Steinhaus sets of period 4 for (a, b, c) iff (a, b, c) is congruent mod 4 to one of the following triples:

(1, 1, 1), (1, 2, 3), (2, 3, 2), (2, 1, 2), (3, 2, 1), and (3, 3, 3).

Proof. This follows from the preceding proposition by a direct computation. □

Definition 2.13. Given a sequence (a_{1}, …, a_{n}) (n ≥ 2) of positive integers. Define

D^{∗} = D^{∗}(a_{1}, …, a_{n}) = {x − y | x, y ∈ A(a_{1}, …, a_{n})}.

It is convenient to include in D^{∗} the negatives of the forbidden distances. Note that if S is a Steinhaus set for (a_{1}, …, a_{n}) and 0 ∈ S (this does not lose generality since any shift of S is still a Steinhaus set), then D^{∗} ∩S = {0}. For a putative period M we denote by D^{∗} (mod M) the set of mod M values of elements of D^{∗}.

Proposition 2.14. Let (a_{1}, …, a_{n}) be a sequence of positive integers and let k ≥ 0. Then there exists a Steinhaus set for (a_{1}, …, a_{n}) of period M = (k + 1)(n + 1) iff

(a) Elements of A(a_{1}, …, a_{n}) have distinct mod M values; and (b) There are integers, 0 = x_{0} < x_{1} < ⋯ < x_{k} < M, such that

x_{j} − x_{i} ∉ D^{∗} (mod M)

for all i < j ≤ k.

Proof. First assume that S is a Steinhaus set for (a_{1}, …, a_{n}) of period M and without loss of generality 0 ∈ S. Clause (a) follows from a similar argument as in the preceding proof. It remains to show (b). From Proposition 2.9 we know that |S ∩ {0, …, M − 1}| = k + 1. Let S ∩ {0, …, M − 1} = {0, x_{1}, …, x_{k}}. Suppose for contradiction that x_{j} −x_{i} = u−v +mM for some m ∈ ℤ and distinct u, v ∈ A(a_{1}, …, a_{n}). But by the periodicity of S we have that x_{j} − mM ∈ S and hence we have two elements x_{i}, x_{j} − mM of S at a forbidden distance d(u, v).

Conversely, assume that (a) and (b) hold. Let S be periodic with period M and S ∩ [0, M) = {0, x_{1}, …, x_{k}} We check that S is a Steinhaus set for A(a_{1}, …, a_{n}) with respect to ℤ. Let X be an isometric copy of A(a_{1}, …, a_{n}). First we argue that |X ∩ S| ≤ 1. For this let x ≠ y ∈ X be both in S. Let x′ = x (mod M) and y′ = y (mod M). Then by (a) x′ ≠ y′ and by periodicity of S we have that x′, y′ ∈ S. So let x′ = x_{j} and y′ = x_{i}. But then, x_{j} − x_{i} ∈ D^{∗} (mod M) contradicting (b).

To see that X ∩ S ≠ ∅, we first consider the case that X is a shift of A(a_{1}, …, a_{n}), i.e., there is some c ∈ ℤ such that X = c+A(a_{1}, …, a_{n}). Since M is a period of S, for any b ∈ ℤ we have that

|(b + S) ∩ [0, M)| = k + 1.

Since S meets each isometric copy of A(a_{1}, …, a_{n}) in at most one point we have that

{−b + S : b ∈ A(a_{1}, …, a_{n})}

are pairwise disjoint. Since M = (k + 1)(n + 1) and

|A(a_{1}, …, a_{n})| = n + 1

it follows that {−b + S : b ∈ A(a_{1}, …, a_{n})} must cover [0, M) and hence all of ℤ. But if c ∈ −b + S then

c + b ∈ S ∩ (c + A(a_{1}, …, a_{n})).

A similar argument can be given for the case that X = c−A(a_{1}, …, a_{n}). □

Corollary 2.15. Let (a_{1}, …, a_{n}) be a sequence of positive integers. Then there exists a Steinhaus set of period 2(n + 1) for (a_{1}, …, a_{n}) iff

(a) Elements of A(a_{1}, …, a_{n}) have distinct mod 2(n + 1) values; and

(b) D^{∗} ≢ {0, …, 2n + 1} (mod 2(n + 1)).

Proof. Clause (b) is equivalent to saying that there is an x such that x ∉ D^{∗} (mod 2(n + 1)). □

Let k ≥ 0 be an integer. Sets of type (1, 1, 4k + 2) or (1, 1, 4k + 4) are Jackson by Example 2.10. Sets of type (1, 1, 4k +1) have Steinhaus sets of period 4 by Proposition 2.11.

Example 2.16. Any set of type (1, 1, 4k + 3) is Jackson.

Proof. The reflection argument gives that if S is a Steinhaus set for (1, 1, 4k +3) then S has a period 8(k +1). When k = 0 the above corollary applies. But in this case D^{∗} = {0, 1, 2, 3, 4, 5, −1, −2, −3, −4, −5} and hence D^{∗} (mod 8) = {0, 1, 2, 3, 4, 5, 6, 7}. Thus there does not exist any Steinhaus set of period 8 for (1, 1, 3) and therefore any set of type (1, 1, 3) is Jackson.

For the general case k > 0 we let M = 8(k + 1) and get that

D^{∗} = {0, ±1, ±2, ±(4k + 3), ±(4k + 4), ±(4k + 5)},

and therefore

D^{∗} (mod M) = {0, 1, 2, 4k + 3, 4k + 4, 4k + 5, 8k + 6, 8k + 7}.

Write B = [3, 4k + 2] ∩ ℕ and C = [4k + 6, 8k + 5] ∩ ℕ. Then B ∪ C is the complement of D^{∗} (mod M) in {0, …, M − 1}. Assume that a Steinhaus set of period M for (1, 1, 4k+3) existed. Then by Proposition 2.14 there are x_{1}, …, x_{2k+1} ∈ B ∪ C with x_{i} − x_{j} ∈ B ∪ C (mod M). Let {x_{1}, …, x_{2k+1}} ∩ B = B_{0}, h = |B_{0}|, C_{0} = {x_{1}, …, x_{2k+1}} ∩ C and l = |C_{0}|. Then h + l = 2k + 1. We note the following facts. For each x ∈ B_{0} such that x ≤ 4k, the numbers 4k + 3 + x, 4k + 4 + x and 4k + 5 + x are in C ∩ (x + D^{∗}), hence in particular are not in C_{0}. Moreover, since 1, 2 ∈ D^{∗}, any two elements of B_{0} differ by at least 2, the two sets of three numbers associated with them have an empty intersection. Using this we obtain the following inequality

l + (h − 1) · 3 + 1 ≤ 4k,

where the left hand side counts the number of elements in C_{0} and the number of elements excluded from C_{0} for being associated with one of the numbers in B_{0} (in a worst case scenario), and the right hand side the size of C. By a symmetric and similar argument we also obtain

h + (l − 1) · 3 + 1 ≤ 4k,

by reversing the roles of B and C. Thus we get

4(h + l) − 4 ≤ 8k or h + l ≤ 2k + 1.

This is not a contradiction yet but it follows from h + l = 2k + 1 that all elements of B and C are accounted for in the above counting in order to establish the inequalities. This is to say that every element of B is either an element of B_{0} or else is associated with an element of C_{0}, and vice versa for elements of C. Now we claim that either 3 ∈ B_{0} or 4k + 6 ∈ C_{0}. It is easy to see that if 4k + 6 ∉ C_{0}, then the only element of B with which it is associated is 3. In the case 3 ∈ B_{0} it is straightforward to check that 3 + 4i ∈ B_{0} for all i = 1, …, k − 1 and 4k + 5 + 4j ∈ C_{0} for all j = 1, …, k, but this is a contradiction since there are only 2k of them. Similarly in the case 4k + 6 ∈ C_{0} it is straightforward to check that 4i ∈ B_{0} for i = 1, …, k and 4k +6+4j ∈ C_{0} for j = 1, …, k − 1, which is a total of 2k of them, contradiction again. □

Note that the Proposition 2.11 and Corollary 2.15 give polynomial time computable criteria for the existence of Steinhaus sets of period n + 1 and 2(n + 1), respectively. However, the criterion in Proposition 2.14 is NP in (a_{1}, …, a_{n}) and M. We do not know whether the existence of Steinhaus sets for a given period is computable in polynomial time. The following corollary provides an easy sufficient condition for this existence.

Question 2.17. Determine all pairs of positive integers a, b such that sets of type (a, a, b) are Jackson.

Corollary 2.18. Let (a_{1}, …, a_{n}) be a sequence of positive integers and let s = a_{1} + ⋯ + a_{n}. If M = (k + 1)(n + 1) > s and there is an integer 0 < x < M such that

{x, 2x, …, kx} ∩ D^{∗} = ∅(mod M),

then there is a Steinhaus set of period M for (a_{1}, …, a_{n}). Consequently, if (b_{1}, …, b_{n}) ≡ (a_{1}, …, a_{n}) (mod M), with (a_{1}, …, a_{n}) and M satisfying the conditions above, then there is also a Steinhaus set of period M for (b_{1}, …, b_{n}).

Proof. If M > s then clause (a) of Proposition 2.14 holds. Let x_{i} = ix for i = 0, 1, …, k. Then for any 0 ≤ i < j ≤ k,

x_{j} − x_{i} = (j − i)x = x_{j−i} ∉ D^{∗} (mod M).

Thus clause (b) of Proposition 2.14 is also verified. The additional part is trivial. However, the point is that b_{1} + ⋯ + b_{n} may not be less than M. □

Example 2.19. Let a and b be odd positive integers with a + b ≡ 0 (mod 4). Then there is a Steinhaus set of period 2(a + b) for (a, b, a).

Proof. Let a + b = 4k and M = 2(a + b) = 8k. Then D^{∗} (mod 8k) = {0, a, 4k−a, 4k, 4k+a, 8k−a}. We have that {2, 4, …, 4k−2}∩D^{∗} = ∅ since both a and 4k − a = b are odd. The proof is completed with the application of the preceding corollary. □

3. Jackson Sets on the Plane

Proposition 3.1 (Jackson). Every three element subset of the plane is Jackson.

Proof. For contradiction suppose there were such an S. Let X = {p, q, r} and suppose p ∈ S. Form the parallelogram pqrp′. Now if p ∈ S then r, q ∉ S and therefor p′ ∈ S since the triangle △pqr is isometric to △p′rq. Let C be the circle centered at p of radius d(p, p′). It follows that every point on C is in S, but this is a contradiction since there is a chord of C with length d(q, r) and therefor there would be an isomorphic copy of X containing at least two points of S. □

Note that this propositional also holds for any three point set in ℝ^{n} for n > 2. A similar argument reflection argument would work for four noncollinear points in ℝ^{3} provided that 4a ≥ e where a is maximum altitude of the tetrahedron and e the minimum edge length.

Proposition 3.2 (Jackson). Every set of n > 1 equally spaced collinear points is Jackson.

Proof. Suppose the points are p_{0}, p_{1}, …, p_{n} written in their natural order. Let p_{n+1} be the next point along the line containing p_{0}, p_{1}, …, p_{n} with the same distance apart. Suppose that p_{0} ∈ S, then p_{1}, …, p_{n} ∉ S and since the set p_{1}, …, p_{n+1} is isometric to the original it must be

[figure: p; q; r; p′; p_{0}; p_{1}; p_{2}; …; p_{n}; p_{n+1}]

Figure 2. Proposition 3.1 and 3.2

that p_{n+1} ∈ S. It follows that the circle of radius d(p_{0}, p_{n+1}) around p_{0} is a subset of S and so we get the same contradiction as in the last proposition. □

This proposition also holds if all gaps but the first gap are equal.

Proposition 3.3. A finite set X ⊆ ℝ^{2} is Jackson iff there exists a finite set F ⊆ ℝ^{2} such that for every S ⊆ F there exists Y ⊆ F an isometric copy of X such that |S ∩ Y | ≠ 1.

Proof. This follows from the compactness theorem. Let

P = {P_{z} : z ∈ ℝ^{2}}

be propositional letters and let

C = {Y ⊆ ℝ^{2} : Y is an isometric copy of X}.

For each Y ∈ C let θ_{Y} , ψ_{Y} be the propositional sentences:

θ_{Y} = ⋁_{z∈Y} P_{z}

ψ_{Y} = ⋀_{z,w∈Y,z≠w}(¬P_{z} ∨ ¬P_{w})

i.e. these say that P_{z} holds for exactly one z ∈ Y. Let

T = {θ_{Y} , ψ_{Y} : Y ∈ C}.

A truth evaluation (model) for T corresponds exactly to a subset S ⊆ ℝ^{2} witnessing that X is not Jackson. By the compactness theorem for propositional logic T since T is inconsistent there is a finite subset of T which is inconsistent. Hence there exist Y_{1}, …, Y_{n} ∈ C such that

Σ = {θ_{Y_{1}}, ψ_{Y_{1}}, θ_{Y_{2}}, ψ_{Y_{2}}, …, θ_{Y_{n}}, ψ_{Y_{n}}}

is inconsistent and therefor F = ∪_{i=1}^{n}Y_{i} does the trick. □

Another proof (but a little round-about) is to quote the Erdos-Bruijn Theorem [1] about graph coloring.

Proposition 3.4. The vertices of the unit square is Jackson. More generally, the vertices of a rectangle with height x and width 1 where x^{2} is a rational number is Jackson.

Proof. First consider the case of the vertices of the unit square. For contradiction assume that S ⊆ ℝ^{2} meets every isomorphic copy the vertices of the unit square in exactly one point. Consider S ∩ ℤ^{2}. There are two possibilities.

Claim 1. Either

• S is disjoint from every other column of ℤ^{2} and for the other columns it contains every other point.

• S is disjoint from every other row of ℤ^{2} and for the other rows

it contains every other point. In either case S ∩ ℤ does not contain two points in the same row or column and at an odd distance.

To see why this is so, suppose the point (i, j) ∈ S. Then the points (i + 1, j), (i, j + 1), (i + 1, j + 1) ∉ S. But since the square next to it must meet S, exactly one of two points (i + 2, j) or (i + 2, j + 1) must be in S.

Case 1. Suppose (i, j) ∈ S and (i + 2, j + 1) ∈ S, i.e., the knight’s move in chess, see figure 3.

In this case the points (i, j + 2) and (i + 2, j + 3) must be in S. This is because the square Q with left lower corner (i + 1, j + 1) rules out the point (i + 1, j + 2) and the point (i + 2, j + 2). Continuing with this argument we see that S must contain all the points (i, j + 2n) and (i + 2, j + 2n + 1) for n ∈ ℤ. It must also be disjoint from the columns i − 1, i + 1, i + 3. An empty column implies that the next column must contain every other point and a column which contains every other point implies that the next column is disjoint.

Case 2. Suppose (i, j) ∈ S and (i − 2, j + 1) ∈ S.

This is symmetrical and again we get that every other column is disjoint from S.

Case 3. Whenever (i, j) ∈ S we have (i ± 2, j) ∈ S.

In this case every row {i + 2n + 1} × ℤ is disjoint from S and so on. This proves Claim 1. Note that by symmetry it is true for every

lattice (isometric copy of ℤ^{2}).

[figure: i; i + 1; i + 2; j; j + 1; j + 2; j + 3; Q]

Figure 3. Knight’s move

Claim 2. Suppose A ∈ S then the circle of radius 4 around A is a subset of S and so we are done.

Consider any three points A, B, C with d(A, B) = 4, d(B, C) = 3 and d(A, C) = 5. To simplify notation assume that A = (0, 0), B = (0, 4), and C = (3, 4).

Case 1. For every odd n ∈ ℤ we have ({n} × ℤ) ∩ S = ∅.

This means in particular that the point D = (1, 4) ∉ S. But since either B or D is in S we have that B ∈ S.

Case 2. For every odd n ∈ ℤ we have (ℤ × {n}) ∩ S = ∅.

In this case every other point on the row ℤ × {4} is in S. If B ∉ S then the point D = (1, 4) ∈ S and so is the point C = (3, 4). But consider the tipped lattice L (see figure 4) with the points (0, 0) and (3, 4) where these points are on the same “column” of L. S must satisfy Claim 1 for L but A and C are on the same column of L and separated by an odd distance (5) which is a contradiction. This does the special case of the unit square.

Now suppose our rectangle has height x and width 1 and x^{2} is a rational number.

Here the basic lattice to consider is

{(m, nx) : m, n ∈ ℤ}.

[figure: A; B; D; C]

Figure 4. Tipped Lattice L

The parity argument we have just given works for any x satisfying

(odd)^{2} + (even)^{2}x^{2} = (odd)^{2}

for some positive odd and even integers, say a^{2} + b^{2}x^{2} = c^{2}. Consider 3 points A, B, and C with d(A, B) = bx, d(B, C) = a, and d(A, C) = c. We claim that if A ∈ S, then B ∈ S. Hence again we get a contradiction since the circle of radius bx centered at A is a subset of S. So suppose for contradiction that B is not in S. Then since the distance from A to B is bx which is even number times the height of the rectangle and since B ∉ S, it must be that S contains every other element of the row on which B, C are on. But since a is odd number this means C ∈ S. Now consider the tipped 1, x-lattice L with the 1 side along the line segment joining A to C. But this length is c which is odd and this cannot happen in a lattice satisfying the analogue of Claim 1.

Fix any positive rational number k/l. If

(2n − 1)^{2} + (2m)^{2}x^{2} = (2n + 1)^{2}

then

x^{2} = \frac{(2n + 1)^{2} − (2n − 1)^{2}}{(2m)^{2}} = \frac{8n}{(2m)^{2}} = \frac{k}{l}

if we take n = 2kl and m = 2l. □

Question 3.5. Is the set of vertices of a rectangle of width ^{3}\sqrt{2} and height 1 Jackson?

Question 3.6. Does there exists S ⊆ ℕ such that S contains exactly one element of every Pythagorean triple x^{2} + y^{2} = z^{2}?

It might be helpful to note that two Pythagorean triples can have at most one point in common, i.e., it impossible to have

x^{2} + y^{2} = z^{2} and y^{2} + z^{2} = w^{2}

in the positive integers, see Sierpiński [11] §10.6.

Question 3.7. (Steprans) Does there exist a finite partition of ℕ, say ℕ = S_{1} ∪ S_{2} ∪ ⋯ ∪ S_{n} such that no S_{i} contains a Pythagorean triple?

Proposition 3.8. For any trapezoid T and ϵ > 0 there exists a trapezoid T′ with corresponding vertices within ϵ of the vertices of T such that the vertices of T′ are Jackson.

Proof. Consider any trapezoid with sides A, B, C, D. (By trapezoid we just mean that two of the sides are parallel.) Assembly four isometric copies into the chevron.

Rotate the chevron around the point p by the angle θ thus taking the point q_{1} to the point q_{2}. Let q_{3} be the image of q_{2} under this rotation. Continue rotating the chevron around p to obtain the sequence q_{1}, q_{2}, q_{3}, q_{4}, … of all equally spaced points on the circle centered at p and with radius d(p, q_{1}).

Now fix ϵ > 0 and consider any continuous transformation of the plane which keeps the points of the new trapezoid within ϵ of the old but changes the angle θ. For example, we could slide the top B a little to left or right keeping the bottom D fixed. This would change the angle θ continuously say from θ_{0} to some slightly large value θ_{1}. To draw the diagram imagine that 0 < θ_{1} − θ_{0} < (.0001)θ_{0}. Fix n such n(θ_{1} − θ_{0}) > 2π. Note that the sequence

q_{1}^{θ_{1}}, q_{2}^{θ_{1}}, q_{3}^{θ_{1}}, …, q_{n}^{θ_{1}}

rotates around p at least one more time than the sequence

q_{1}^{θ_{0}}, q_{2}^{θ_{0}}, q_{3}^{θ_{0}}, …, q_{n}^{θ_{0}}.

So by the intermediate value theorem there is a θ with θ_{0} ≤ θ ≤ θ_{1} with q_{n}^{θ} = q_{0}^{θ} and another where q_{n}^{θ} is on the opposite side of p to q_{0}^{θ}.

[figure: A; A; B; D; B; C; C; D; B; D; A; A]

Figure 5. Four trapezoids

[figure: p; r; q_{2}; q_{1}; θ]

Figure 6. Chevron This implies that there exists θ with θ_{0} ≤ θ ≤ θ_{1} such that the d(q_{1}^{θ}, q_{n}^{θ}) is exactly the length of say the side B. Let T′ be this trapezoid.

Now we prove that set of vertices of T′ is Jackson. Suppose for contraction that S ⊆ ℝ^{2} meets every isomorphic copy of the vertices of T′ in exactly one point.

Suppose p ∈ S. Then we know that the circle with center p and radius d(p, r) cannot be a subset S. Hence by rotating S we may assume that r ∉ S. Since each of the rightmost two trapezoids must meet S, it must be that both q_{1} and q_{2} are in S. If rotate the chevron around p by θ we note that since q_{2} ∈ S it must be that q_{3} ∈ S. Similarly it must be that all q_{i} ∈ S in particular q_{n} ∈ S. This is a contradiction since d(q_{1}, q_{n}) is the length of B so there is an isomorphic copy of T′ containing two points of S.

Other distortions of the trapezoid T which would work as well to obtain T′ would be to

• change the height while leaving B and D the same length or • taking any of the vertices and move it slightly to right while

fixing the other vertices. In short anything which continuously changes the angle θ. For example, if T is a parallelogram, then T′ can be taken to be a parallelogram with the same length sides but a slight change in the interior angles. □

This proposition suggests the obvious question of whether every four point set is within ϵ of a Jackson set. While the above argument shows that every four point collinear set is ϵ-close to a trapezoid, we did not know whether every four point collinear set is ϵ-close to a four point collinear set which is Jackson. This question was answered by Louis Leung:

Proposition 3.9. (Leung) Every 4-point collinear set is ϵ-close to a 4-point collinear set which is Jackson.

Proof. Let {A, B, C, D} be a 4-point set on a straight line l. Reflect the line across the midpoint of the line segment \overline{CD}. We let A′, B′ be image of A, B on l, hence B′ − D = C − B and A′ − B′ = B − A. Note that by our usual reflection argument, if A is in a Steinhaus set S then exactly one of B′ or A′ lies in S.

We consider two circles C_{1} and C_{2} centered at A whose radii are d(A, A′) and d(A, B′), respectively. Let α, β be the angles subtended by a chord of length d(D, C) in C_{1} and C_{2}, respectively.

Suppose ϵ > 0 is fixed. Without loss of generality we may assume ϵ < d(B, C). Let C′′ be a point between B and C and D′′ a point between D and B′ so that d(C, C′′) = d(D, D′′) = δ where 0 < δ < ϵ, and α′′, β′′ be the angles subtended by a chord of length d(D′′, C′′) in C_{1} and C_{2}, respectively. Since d(C, D) < d(C′′, D′′), α′′ + β′′ > α + β and there is n ∈ ℕ such that n(α′′+β′′−(α+β)) > 2π. By the intermediate value theorem, there is a positive 0 < κ < ϵ such that if C̃ is between C and C′′, D̃ is between D and D′′, and d(D̃, D) = d(C̃, C) = κ, then the corresponding angles α̃ and β̃ (the angles subtended by a chord of length d(C̃, D̃) in C_{1} and C_{2}, respectively) satisfy

n(α̃ + β̃) = 2mπ + θ

for some m, n ∈ ℕ where θ is the angle subtended by a chord of length d(A, B) in C_{1}.

Claim {A, B, C̃, D̃} is Jackson.

Proof. Suppose not. Let S be a Steinhaus set for {A, B, C̃, D̃}. By translating the set if necessary, we may assume A ∈ S. Let A′, B′, C_{1} and C_{2} be defined as above. Note {C̃, D̃, B′, A′} is an isometric copy of {A, B, C̃, D̃}. By our definition of S, if x and y lie on the same half line originating at A such that x ∈ C_{1} and y ∈ C_{2}, either x or y (but not both) must be a member of S. (We may think of, by rotation if necessary, x as A′ and y as B′.) Note that S must contain at least one point in C_{1}, for otherwise C_{2} ⊂ S and C_{2} has a chord of length d(A, B), a contradiction.

Therefore we may assume A′ ∈ S. We let A0^{′} = A′ and An+1^{′} be the image of An^{′} after rotation by α̃+β̃ with respect to A. By our definition of α̃, β̃ and S, We know Am^{′} ∈ S for all m ∈ ℕ. By letting m = n where n is as given in equation (1), we know that S contains 2 points a distance of d(A, B) apart, contradicting our choice of S.

Therefore {A, B, C̃, D̃} is Jackson. □ The following still seems to be open:

Question 3.10. Is every four point set in ℝ ϵ-close to a four point subset of ℝ which is Jackson?

References

[1] de Bruijn, N. G.; Erdös, P.; A colour problem for infinite graphs and a problem in the theory of relations. Nederl. Akad. Wetensch. Proc. Ser. A. 54 Indagationes Math. 13, (1951). 369–373.

[2] Eggleton, R. B.; Erdös, P.; Skilton, D. K.; Colouring prime distance graphs. Graphs Combin. 6 (1990), no. 1, 17–32.

[3] Falconer, K. J.; The realization of distances in measurable subsets covering R^{n}. J. Combin. Theory Ser. A 31 (1981), no. 2, 184–189.

[4] Jackson, Steve; Mauldin, R. Daniel; On a lattice problem of H. Steinhaus. J. Amer. Math. Soc. 15 (2002), no. 4, 817–856

[5] Jackson, Steve; Mauldin, R. Daniel; Sets meeting isometric copies of the lattice Z^{2} in exactly one point. Proc. Natl. Acad. Sci. USA 99 (2002), no. 25, 15883– 15887.

[6] Jackson, Steve; Mauldin, R. Daniel; Survey of the Steinhaus tiling problem. Bull. Symbolic Logic 9 (2003), no. 3, 335–361.

[7] Klee, Victor; Wagon, Stan; Old and new unsolved problems in plane geometry and number theory. The Dolciani Mathematical Expositions, 11. Mathematical Association of America, Washington, DC, 1991.

[8] Komjáth, Péter; A lattice-point problem of Steinhaus. Quart. J. Math. Oxford Ser. (2) 43 (1992), no. 170, 235–241.

[9] Komjáth, P.; A coloring result for the plane. J. Appl. Anal. 5 (1999), no. 1, 113–117.

[10] Schmerl, James H.; Coloring ℝ^{n}. Trans. Amer. Math. Soc. 354 (2002), no. 3, 967–974.

[11] Sierpiński, Wacław; Pythagorean triangles. Translated from the Polish by Ambikeshwar Sharma. Reprint of the 1962 edition [MR0191870 (33 #97)]. Dover Publications, Inc., Mineola, NY, 2003. x+107 pp. ISBN: 0-486-43278-5 11D09

[12] Zhu, Xuding; Circular chromatic number of distance graphs with distance sets of cardinality 3. J. Graph Theory 41 (2002), no. 3, 195–207.

Department of Mathematics, PO Box 311430, University of North Texas, Denton, TX 76203

E-mail address: sgao@unt.edu

Department of Mathematics, University of Wisconsin-Madison, 480 Lincoln Drive, Madison, WI 53706

  E-mail address: miller@math.wisc.edu       www.math.wisc.edu/∼miller

Department of Mathematics, University of Toronto, Ontario, CA, M5S 3G3

  E-mail address: weiss@math.toronto.edu