Reconstructing subsets of reals

A.J. Radcliffe ^{1}

Department of Mathematics and Statistics

University of Nebraska-Lincoln

Lincoln, NE 68588-0323

jradclif@math.unl.edu

A.D. Scott Department of Mathematics

University College

Gower Street London WC1E 6BT

A.Scott@ucl.ac.uk

Submitted: November 24, 1998; Accepted: March 15, 1999

1Partially supported by NSF Grant DMS-9401351

Abstract

We consider the problem of reconstructing a set of real numbers up to translation from the multiset of its subsets of fixed size, given up to translation. This is impossible in general: for instance almost all subsets of ℤ contain infinitely many translates of every finite subset of ℤ. We therefore restrict our attention to subsets of ℝ which are locally finite; those which contain only finitely many translates of any given finite set of size at least 2.

We prove that every locally finite subset of ℝ is reconstructible from the multiset of its 3-subsets, given up to translation.

Primary: 05E99; Secondary: 05C60

1 Introduction.

Reconstructing combinatorial objects from information about their subobjects is a long-standing problem. The Reconstruction Conjecture and the Edge Reconstruction Conjecture both deal with the problem of reconstructing a graph from a multiset of subgraphs; in one case the collection of all induced subgraphs with one fewer vertex, in the other the collection of all subgraphs with one fewer edge (see Bondy [2] and Bondy and Hemminger [3]).

The very general problem is that of reconstructing a combinatorial object (up to isomorphism) from the collection of isomorphism classes of its subobjects. Isomorphism plays a crucial rôle. Thus it seems that the natural ingredients for a reconstruction problem are a group action (to provide a notion of isomorphism) and an idea of what constitutes a subobject. Reconstruction problems have been considered from this perspective by, for instance, Alon, Caro, Krasikov and Roditty [1], Radcliffe and Scott [11], [10], Cameron [4], [5], and Mnukhin [7], [8], [9].

In this paper we consider the problem of reconstructing subsets of the groups ℤ, ℚ, and ℝ from the multiset of isomorphism classes of their subsets of fixed size, where two subsets are isomorphic if one subset is a translate of the other. Where the subsets have size k we call this collection the k-deck.

Maybe the first thing to notice is that for |A| ≥ k one can reconstruct the l-deck of A from the k-deck for any l ≤ k. This is a straightforward translation of Kelly’s lemma (see [2]). On the other hand if |A| < k then the k-deck of A is empty, and therefore A cannot be distinguished from any other subset of size strictly less than k. It makes the statement of our theorems slightly easier if we use a definition of deck for which this issue does not arise. The definition we adopt below regards the deck as a function on multisets of size k. It is straightforward to check that this form of the k-deck can be determined from the deck as defined above, provided |A| ≥ k.

Definition 1 Let A be a subset of 𝔽, where 𝔽 is one of ℤ, ℚ, or ℝ. The k-deck of A is the function defined on multisets Y of size k from 𝔽 by

d_{A,k}(Y) = |{i ∈ 𝔽 : supp(Y + i) ⊂ A}|,

where supp(Y) is the set of elements of Y, considered without multiplicity. We say that A is reconstructible from its k-deck if we can deduce A up to translation from its k-deck; in other words, we have

d_{B,k} ≡ d_{A,k} ⇒ B = A + i, for some i ∈ 𝔽.

More generally we say that a function of A is reconstructible from the k-deck of A if its value can be determined from d_{A,k}.

Certain subtleties arise since the groups involved are infinite. It may be that the k-deck of A ⊂ 𝔽 takes the value ∞ on some finite (multi)sets. In fact, for any fixed finite subset F ⊂ ℤ, almost all subsets of ℤ (with respect to the obvious symmetric probability measure on P(ℤ)) contain infinitely many translates of F. Thus it is trivial to find, for all k ≥ 1, two subsets of ℤ with the same k-deck which are not translates of one another.

For this reason we restrict our attention to subsets A ⊂ 𝔽 for which the 2-deck (and a fortiori the k-deck for all k ≥ 2) takes only finite values, or equivalently, every distance occurs at most fintely many times. We shall call such sets locally finite.

It is easily seen that every finite subset A ⊂ ℝ can be reconstructed from its 3-deck, d_{A,3}: indeed, let n = diam A := max A − min A; then

A ≃ {0, n} ∪ {r : d_{A,3}({0, r, n}) > 0}.

The 2-deck is not, however, in general enough. For instance, if A and B are finite sets of reals then A + B and A − B have the same 2-deck.

Our aim in this note is to prove a reconstruction result for locally finite sets of reals. We begin by proving a result for ℤ and work in stages towards ℝ. We shall write A ≃ B if A is a translation of B.

Theorem 1 Let A ⊂ ℤ be locally finite. Then A is reconstructible from its 3-deck. In other words, if A, B ⊂ ℤ have the same 3-deck then A ≃ B.

We shall first prove a lemma. For subsets A, B ⊂ ℤ, we define A + B to be the multiset of all a + b with a ∈ A and b ∈ B. (This multiset might of course take infinte values). Thus, for finite A and B, if we identify A with a(x) = ∑_{i∈A} x^{i} and B with b(x) = ∑_{i∈B} x^{i}, then A + B can be identified with a(x)b(x), where the coefficient of x^{i} in a(x)b(x) is the multiplicity of i in the sum A + B.

If L is a multiset of ℤ we write m_{L}(i) for the multiplicity of i in L.

Lemma 2 Let A, B, C ⊂ ℤ be finite and suppose that A+C = B +C. Then A = B.

Proof. Straightforward by induction on |A|, noting that min(A + C) = min A + min C.

Lemma 3 If A, B ⊂ ℤ are locally finite, infinite sets with A △ B finite, and C is a finite set with A + C = B + C then A = B.

Proof. Let A_{0} = A \ B, let B_{0} = B \ A, and set R = A ∩ B. Now for all i we have

m_{A_{0}+C}(i) = m_{A+C}(i) − m_{R+C}(i)
= m_{B+C}(i) − m_{R+C}(i)
= m_{B_{0}+C}(i).

Thus A_{0} + C = B_{0} + C and it follows from Lemma 2 that A_{0} = B_{0} and so A = B.

Lemma 4 If A, B ⊂ ℤ are locally finite, infinite sets, and C is a finite set with A + C = B + C then A = B.

Proof. We may suppose, without loss of generality, that 0 ∈ C. Now let S = {i : C + i ⊂ A + C} and c = diam(C). We aim to show that, except for a finite amount of confusion, we have S = A. To this end, let N be sufficiently large such that for all distinct a, a′ ∈ A with |a| > N we have |a′ − a| > 4c and for all distinct b, b′ ∈ B with |b| > N we have |b′ − b| > 4c. (Such an N exists since A and B are locally finite.) Suppose now that k, with |k| > N +4c, belongs to two sets from {C+i : i ∈ S}, say k ∈ (C+i)∩(C+j). Define D = (C + i) ∪ (C + j). Since diam(D) > c, while D ⊂ A + C, there must be distinct elements a_{1}, a_{2} ∈ A such that D meets both C + a_{1} and C + a_{2}. But this is impossible, for then |a_{1} − a_{2}| ≤ 4c, while |a_{1}| > N. Thus every k ∈ A+C with |k| > N +4c belongs to exactly one set C +i. It follows that i ∈ A, and by the same reasoning i ∈ B.

Now set R = {i ∈ S : |i| > N + 4c}. We have just established that R ⊂ A and R ⊂ B, and obviously R ⊃ {a ∈ A : |a| > N + 4c} and R ⊃ {b ∈ B : |b| > N + 4c}. Thus AΔB is finite, and by Lemma 3 the result is established.

Lemma 5 Let A, B ⊂ ℤ be locally finite infinite sets and let C, D ⊂ ℤ be finite. If A + C = B + D then A ≃ B and C ≃ D.

Proof. We may clearly assume that min C = min D = 0. Under this hypothesis we will prove that A = B and C = D.

We will show that C (and equally D) is the largest set such that infinitely many translates of C are contained in A + C = B + D. Suppose then that A+C contains infinitely many translates of some set E and that no translate of E is a subset of C. Let E_{1}, E_{2}, … be translates of E, where E_{i} ⊂ A + C and | min E_{i}| → ∞ as i → ∞. Since E is contained in no translate of C, every E_{i} must meet at least two translates of C, say C_{a_{i}} and C_{b_{i}}, where a_{i} and b_{i} are distinct elements of A. Thus there are distinct a_{i}, b_{i} ∈ A with

|a_{i} − b_{i}| ≤ 2 diam(C) + diam(E)

and |a_{i}| → ∞; since there are only finitely many possibilities for a_{i} − b_{i} and infinitely many a_{i}, some distance must occur infinitely many times, which contradicts the assumption that A is locally finite.

We conclude that C is the largest set (uniquely defined up to translation) that has infinitely many translates as subsets of A+C. Hence we have C ≃ D and so C ≡ D, since min C = min D. Thus A + C = B + D = B + C, and by Lemma 4, A = B. Proof. [of Theorem 1] If A is finite then it is easily reconstructed from its 3-deck, as noted above. Thus we may assume that A is infinite.

Let k be a difference that occurs in A (i.e. there are a_{1}, a_{2} ∈ A with a_{1} − a_{2} = k). We shall show that A can be reconstructed from its 3-deck; moreover, it can be reconstructed from its 3-deck restricted to multisets of the form {0, k, α}. Indeed, let B be another set with the same 3-deck. Define

X_{A} = {a ∈ A : a + k ∈ A}

and

X_{B} = {b ∈ B : b + k ∈ B}.

Then, translating if necessary, we may assume that min X_{A} = min X_{B}. We claim now that A = B.

In order to prove our result it is enough to show that −A+X_{A} = −B+X_{B}, for then the result follows immediately from Lemma 5: since −A = −B we also have A = B.

Now for i ∈ ℤ, the multiplicity of i in −A + X_{A} is

|{j : j ∈ X_{A}, i − j ∈ −A} = |{j : j ∈ X_{A}, j − i ∈ A}|
= |{j : j, j + k, j − i ∈ A}|.

If i ≠ 0, −k, then this is the multiplicity of {0, i, i + k} in the 3-deck of A; if i = 0 or i = −k then this is |X_{A}|, the multiplicity of {0, k} in the 2-deck of A. Clearly, similar calculations hold for B, so −A + X_{A} = −B + X_{B}.

Theorem 6 Lemmas 2, 3, 4, and 5 hold in ℤ^{n} for all positive integers n. Moreover if A, B ⊂ ℤ^{n} have the same 3-deck then A ≃ B.

Proof. The proofs are almost identical to those for the corresponding results about ℤ. We use the norm |a| = ∥a∥_{2}, and order ℤ^{n} lexicographically, so a ≤ b if the first nonzero coordinate of b − a is positive. The assumptions min C = min D in the proof of Lemma 2 and min X_{A} = min X_{B} in the proof of Theorem 1 then make sense. Moreover, the claim in the proof of Lemma 4 that diam(D) > diam(C) is easily seen to hold in ℤ^{n} also: suppose D = (C+i)∪(C+j) and x, y ∈ C satisfy |x−y| = diam(C). Let v = i−j ≠ 0. Now |(x + i) − (y + j)| = |(x − y) + v| and |(x + j) − (y + i)| = |(x − y) − v| and one of these two norms is strictly greater than |x − y| = diam(C) (by the strict convexity of the norm we have chosen).

Theorem 7 Let A, B ⊂ ℚ be locally finite and have the same 3-deck, then A ≃ B.

Proof. Suppose A and B are locally finite subsets of ℚ with the same 3deck. Let k be some distance that occurs in A, and again define X_{A} = {a ∈ A : a + k ∈ A} and X_{B} = {b ∈ B : b + k ∈ B} as in the proof of Theorem 1. We may assume min X_{A} = min X_{B} = 0. Now suppose n is an integer such that 1/n divides k and all differences in X_{A} and X_{B}. That is, nk ∈ ℤ and for all q, r ∈ X_{A} ∪ X_{B} we have n(q − r) ∈ ℤ. In particular nq ∈ ℤ for all q ∈ X_{A} ∪ X_{B}. We will show that for all i we have

A ∩ \frac{1}{in}ℤ = B ∩ \frac{1}{in}ℤ

Since ℚ = ⋃_{i≥1} \frac{1}{in}ℤ the result will then be proved.

As in the proof of Theorem 1, it is enough to show that the 3-decks of A∩ \frac{1}{in}ℤ and B ∩ \frac{1}{in}ℤ, restricted to multisets of form \{0, k, α\}, are equal. Now if a + {0, k, α} ⊂ A then a ∈ X_{A}, and so

a + \{0, k, α\} ⊂ A ∩ \frac{1}{in}ℤ  ⟺  a + α ∈ \frac{1}{in}ℤ
⟺  α ∈ \frac{1}{in}ℤ.

Thus the relevant parts of the 3-decks of A ∩ \frac{1}{in}ℤ and B ∩ \frac{1}{in}ℤ are equal, and hence A ∩ \frac{1}{in}ℤ = B ∩ \frac{1}{in}ℤ.

Theorem 8 Let A ⊂ ℚ^{n} be locally finite. Then A is reconstructible from its 3-deck.

Proof. Similar to the proof of Theorem 7, with modifications as indicated in the proof of Theorem 6.

Theorem 9 Let A ⊂ ℝ be locally finite. Then A is reconstructible from its 3-deck.

Proof. Let {q : q ∈ I} be a Hamel basis for ℝ over ℚ, where the set I is well-ordered by ≺. This induces a total ordering on ℝ by defining x < y iff y − x = ∑_{i=1}^{n} a_{i}q_{i} with q_{1} ≺ q_{2} ≺ ⋯ ≺ q_{n} and a_{1} > 0. Given a subset S ⊂ R we write ⟨S⟩ for the collection of finite ℚ -linear combinations of elements of S.

Now suppose that A, B ⊂ ℝ are locally finite, and that the 3-decks of A and B are the same. Let r be a distance that occurs in A and let X_{A} = {a ∈ A : a + r ∈ A}, and X_{B} = {b ∈ B : b + r ∈ B}. We may assume that min X_{A} = min X_{B} = 0. Let I_{0} ⊂ I be a finite subset of I such that x−y ∈ ⟨I_{0}⟩ for all x, y ∈ X_{A} ∪X_{B}, and also r ∈ ⟨I_{0}⟩. Such a subset exists, since X_{A} ∪X_{B} is finite and every element of ℝ can be written as a ℚ -linear combination of a finite set of elements from I.

We will show that for finite subsets J with I_{0} ⊂ J ⊂ I, the sets A ∩ ⟨J⟩ and B ∩ ⟨J⟩ are equal, from which it easily follows that A = B. Consider then such a J. If a + {0, r, α} ⊂ A then a ∈ X_{A} and

a + {0, r, α} ⊂ A ∩ ⟨J⟩  ⟺  a + α ∈ ⟨J⟩
⟺  α ∈ ⟨J⟩ .

Since ⟨J⟩ is isomorphic to ℚ^{N}, for some N, and, by the argument above, the 3-decks of A ∩ ⟨J⟩ and B ∩ ⟨J⟩ restricted to multisets of form {0, r, α} are the same, it follows from Theorem 8 that A ∩ ⟨J⟩ = B ∩ ⟨J⟩. Since ⋃_{J⊃I_{0}} ⟨J⟩ = ℝ, we have that A = B.

It would be interesting to have a measure-theoretic version of this result. Let S be a Lebesgue-measurable set of reals, and for every finite set X, define S(X) = λ(x : X + x ⊂ S). Call S locally finite if S(X) is finite whenever |X| > 1. We regard sets X, Y as equivalent if λ(X △ (Y + t)) = 0 for some real number t. Can we reconstruct every set of finite measure from its 3deck? Can we reconstruct every locally finite set from its 3-deck? Or from the k-deck for sufficiently large k?

References

[1] N. Alon, Y. Caro, I. Krasikov and Y. Roditty, Combinatorial reconstruction problems, J. Comb. Theory, Ser. B 47 (1989), 153–161

[2] J. A. Bondy, A graph reconstructor’s manual, in Surveys in Combinatorics, 1991, ed. A.D. Keedwell, LMS Lecture Note Series 166, 221–252

[3] J. A. Bondy and R. L. Hemminger, Graph reconstruction – a survey, J. Graph Theory 1 (1977), 227–268

[4] P. J. Cameron, Stories from the age of reconstruction, Festschrift for C. St. J. A. Nash-Williams, Congr. Numer. 113 (1996), 31–41

[5] P. J. Cameron, Some open problems on permutation groups, in M. W. Liebeck and J. Saxl, eds, Groups, Combinatorics and Geometry, London Mathematical Society Lecture Notes 165, CUP, 1992, 340-351

[6] I. Krasikov and Y. Roddity, On a reconstruction problem for sequences, J. Comb. Theory, Ser. A 77 (1977), 344-348

[7] V. B. Mnukhin, The k-orbit reconstruction and the orbit algebra, Acta Appl. Math. 29 (1992), 83–117

[8] V. B. Mnukhin, The reconstruction of oriented necklaces, J. Combinatorics, Information and System Sciences, 20 (95), 261-272

[9] V. B. Mnukhin, The k-orbit reconstruction for Abelian and Hamiltonian groups, Acta Applicandae Mathematicae 52 (98), 149-162

[10] A. J. Radcliffe and A. D. Scott, Reconstruction subsets of ℤ_{n}, J. Comb. Theory, Ser. A 83 (98), 169-187

[11] A. J. Radcliffe and A. D. Scott, Reconstructing subsets of non-Abelian groups, manuscript.