% A latex file for a 7 page document
\documentclass[12pt,titlepage]{article}
\usepackage{amsmath,amssymb,theorem}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}

{\theorembodyfont{\rmfamily}
\newtheorem{remark}{Remark}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}
}

\newcommand\proof{\noindent {\bf Proof.\ }}
\newcommand\less{\setminus}
\newcommand\of{\subset}

\def\case#1.#2{{\noindent{\bf Case #1. }#2\par}}
\def\contains{\supset}
\def\setof#1#2{{\left\{#1\,:\,#2\right\}}}
\def\set#1{\left\{ {#1} \right\}}
\def\wo{\setminus}
\def\iso{\simeq}
\def\actingon{\rightharpoonup}
\def\implies{\Rightarrow}
 \def\sqr{{\vrule height6pt width6pt depth 0pt}}
\def\blot{{\unskip\nobreak\hfil\penalty50
\hskip2em\hbox{}\nobreak\hfill$\sqr$\finalhyphendemerits=0\parfillskip=0pt
\smallskip\par}}

\def\R{{\mathbb R}}
\def\N{{\mathbb N}}
\def\C{{\mathbb C}}
\def\Z{{\mathbb Z}}
\def\Q{{\mathbb Q}\,}
\def\F{{\mathbb F}}
\def\P{{\cal P}}

\def\supp{\mathop{\rm supp}}
\def\ind{\mathop{\rm ind}}
\def\diam{\mathop{\rm diam}}
\def\ns{\emptyset}
\def\<#1>{\left\langle #1 \right\rangle}

\begin{document}

\title {Reconstructing subsets of reals}
\author{A.J. Radcliffe \thanks{Partially supported by NSF Grant
DMS-9401351}\\ Department of Mathematics and Statistics\\
University of Nebraska-Lincoln \\
Lincoln, NE 68588-0323 \\
{\small\texttt{jradclif@math.unl.edu}} \\
\and A.D. Scott \\ Department of Mathematics \\
University College \\
Gower Street \\
London WC1E 6BT \\
{\small\texttt{A.Scott@ucl.ac.uk}}}
\date{Submitted: November 24, 1998; Accepted: March 15, 1999}
\maketitle
\begin{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 $\Z$ contain infinitely many translates of every finite subset of $\Z$. We therefore restrict our attention to subsets of $\R$ which are {\em 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 $\R$ is reconstructible from the multiset of its 3-subsets, given up to translation.

\bigskip\bigskip
\centerline{Primary: 05E99; Secondary: 05C60}

\end{abstract}

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{6} (1999), \#R20\hfill}
\thispagestyle{empty}

\section {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 \cite{Bo} and
Bondy and Hemminger \cite{BoHe}).

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\^ole.
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 \cite{AlCaKrRo}, Radcliffe and Scott \cite{RS}, \cite{RSb}, Cameron \cite{Ca}, \cite{Cab}, and Mnukhin \cite{Mnuk}, \cite{Mnukb}, \cite{Mnukc}.
 
In this paper we consider the problem of reconstructing subsets
of the groups $\Z$, $\Q$, and $\R$ 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 {\em $k$-deck}.

Maybe the first thing to notice is that for $|A| \ge k$ one can
reconstruct the $l$-deck of $A$ from the $k$-deck for any $l \le k$.
This is a straightforward translation of Kelly's lemma (see \cite{Bo}). 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| \ge k$.

\begin{definition}
Let $A$ be a subset of $\F$, where $\F$ is one of $\Z$, $\Q$, or $\R$.
The {\em $k$-deck} of $A$ is the function defined on multisets $Y$
of size $k$ from $\F$ by
$$d_{A,k}(Y)=|\setof{i\in\F}{\supp(Y+i)\subset A}|,$$
where $\supp(Y)$ is the set of elements of $Y$, considered without
multiplicity.
We say that $A$ is {\em 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}\equiv d_{A,k}\implies B=A+i,\hbox{for some $i\in\F$.}$$
More generally we say that a function of $A$ is {\em reconstructible
from the $k$-deck of $A$} if its value can be determined from $d_{A,k}$. 
\end{definition}

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

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

It is easily seen that every finite subset $A\subset\R$ can be reconstructed  
from its
3-deck, $d_{A,3}$:
indeed, let $n=\diam A :=\max A-\min A$; then
$$A\iso \set{0,n}\cup \setof{r}{d_{A,3}(\set{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 $\Z$ and work in stages towards $\R$.
We shall write $A\iso B$ if $A$ is a translation of $B$.

\begin{theorem}\label{theorem:Z}
Let $A\subset\Z$ be locally finite.  Then $A$ is reconstructible from its 3-deck.
In other words, if $A,B \subset \Z$ have the same 3-deck then $A \iso B$.
\end{theorem}

We shall first prove a lemma.  For subsets $A,B\subset\Z$, we define $A+B$ to be 
the multiset of all $a+b$ with $a\in A$ and $b\in B$. (This multiset might of course take 
infinte values). 
Thus, for finite $A$ and $B$, if we identify $A$ with $a(x)=\sum_{i\in A}x^i$ and $B$ with 
$b(x)=\sum_{i\in 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 $\Z$ we write $m_L(i)$ for the multiplicity of $i$ in $L$.

\begin{lemma}\label{lemma:finite+finite}
Let $A, B, C \subset \Z$ be finite and suppose that $A+C = B+C$. Then $A=B$.
\end{lemma}

\proof Straightforward by induction on $|A|$, noting that $\min(A+C) = \min A + \min C$.
\blot

\begin{lemma}\label{lemma:finitedistortion+finite}
If $A, B \subset \Z$ are locally finite, infinite sets with $A \bigtriangleup B$  
finite, and $C$
is a finite set with $A+C = B+C$ then $A = B$.
\end{lemma}

\proof Let $A_0 = A\wo B$, let $B_0 = B\wo A$, and set $R = A \cap B$. 
Now for
all $i$ we have
\begin{eqnarray*}
m_{A_0+C}(i) &=& m_{A+C}(i) - m_{R+C}(i) \cr
	&=& m_{B+C}(i) - m_{R+C}(i) \cr
	&=& m_{B_0+C}(i) . \cr
\end{eqnarray*}
Thus $A_0+C = B_0+C$ and it follows from Lemma \ref{lemma:finite+finite} that $A_0 = B_0$
and so $A=B$.
\blot

\begin{lemma}\label{lemma:locallyfinite+finite}
If $A,B \subset\Z$ are locally finite, infinite sets, and $C$ is a
finite set with $A+C = B+C$ then $A=B$.
\end{lemma}

\proof 
We may suppose, without loss of generality, that $0 \in C$. Now let
$S = \setof{i}{C+i \subset 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'\in A$ with $|a| > N$  we have $|a'-a| > 4c$ and for all distinct $b,b'\in 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\in S\}$, say 
$k\in (C+i)\cap(C+j)$. Define $D=(C+i)\cup(C+j)$. Since $\diam(D)>c$, while $D \subset A+C$, there must be distinct elements $a_1, a_2 \in A$ such that $D$ meets both
$C+a_1$ and $C+a_2$. But this is impossible, for then $|a_1-a_2|\le4c$, 
while $|a_1| > N$. Thus every $k \in A+C$ with $|k| > N+4c$ belongs to
exactly one set $C+i$.  It follows that $i\in A$, and by the same reasoning $i\in B$.

Now set $R = \setof{i\in S}{|i| > N + 4c}$. We have just established that
$R \subset  A$ and $R\subset B$, and obviously $R \contains \setof{a\in A}{|a| > N+
4c}$ and $R \contains \setof{b\in B}{|b| > N+4c}$. Thus $A  
\Delta B$ is
 finite, and by Lemma \ref{lemma:finitedistortion+finite} the result is  
established.
\blot


\begin{lemma}\label{lemma:iso}
Let $A,B\subset\Z$ be locally finite infinite sets and let $C,D\subset\Z$ be  
finite.  If
$A+C=B+D$ then $A\iso B$ and $C\iso D.$
\end{lemma}

\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, \ldots$ be translates  
of $E$, where
$E_i\subset A+C$ and $|\min E_i |\to\infty$ as $i\to\infty$.  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 \in A$ with
$$|a_i-b_i|\le 2\diam(C)+\diam(E)$$
and $|a_i|\to\infty$; 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\iso D$ and so 
$C\equiv D$, since $\min C=\min D$.  Thus $A+C=B+D=B+C$, and by
Lemma \ref{lemma:locallyfinite+finite}, $A=B$. 
\blot

\proof {\bf[of Theorem \ref{theorem:Z}]}
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\in 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 $\set{0,k,\alpha}$. Indeed, let $B$ be another set with the same  
3-deck.  Define
$$X_A=\setof{a\in A}{a+k\in A}$$
and
$$X_B=\setof{b\in B}{b+k\in 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 \ref{lemma:iso}: since $-A=-B$ we also
have $A=B$.

Now for $i\in \Z$, the multiplicity of $i$ in $-A+X_A$ is
\begin{eqnarray*}
|\setof{j}{j\in X_A, i-j\in-A}&=&|\setof{j}{j\in X_A,j-i\in A}|\\
&=&|\setof{j}{j,j+k,j-i\in A}|.
\end{eqnarray*}
If $i\ne0,-k$, then this is the multiplicity of $\set{0,i,i+k}$ in the  
3-deck of $A$; if
$i=0$ or $i=-k$ then this is $|X_A|$, the multiplicity of $\set{0,k}$ in the  
2-deck of
$A$.  Clearly, similar calculations hold for $B$, so $-A+X_A=-B+X_B$.
\blot

\begin{theorem}\label{theorem:general}
Lemmas \ref{lemma:finite+finite}, \ref{lemma:finitedistortion+finite},
\ref{lemma:locallyfinite+finite}, and \ref{lemma:iso}
hold in $\Z^n$ for all positive integers $n$. Moreover if $A, B \subset  
\Z^n$ have the same
3-deck then $A \iso B$.
\end{theorem}

\proof  The proofs are almost identical to those for the corresponding  
results about
$\Z$. We use the norm $|a| = \|a\|_2$, and order  $\Z^n$ lexicographically,  
so $a\le b$ if the first
nonzero coordinate of $b-a$ is positive. The assumptions $\min C=\min D$ in the 
proof of Lemma \ref{lemma:finite+finite} and $\min X_A=\min X_B$ in the proof of Theorem \ref{theorem:Z} then make 
sense. Moreover, the claim in the proof of Lemma \ref{lemma:locallyfinite+finite} that 
$\diam(D) > \diam(C)$ is easily seen to hold in $\Z^n$ also: suppose $D = (C+i) \cup (C+j)$
and $x,y \in C$ satisfy $|x-y| = \diam(C)$. Let $v = i-j \not= 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).
\blot

\begin{theorem}\label{theorem:Q}
Let $A, B\subset\Q$ be locally finite and have the same 3-deck, then
$A \iso B$.
\end{theorem}

\proof Suppose $A$ and $B$ are locally finite subsets of $\Q$ with the same  
3-deck.
Let $k$ be some
distance that occurs in $A$, and  again define $X_A =\setof{a\in A}{a+k\in A} $ 
and $X_B=  \setof{b\in B}{b+k\in 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 \in \Z$ and for all $q,r \in X_A \cup X_B$ we have  
$n(q-r) \in \Z$. In
particular $nq \in \Z$ for all $q \in X_A \cup X_B$.
We will show that for all $i$ we have
$$A\cap\frac{1}{in}\Z = B\cap\frac{1}{in}\Z$$
Since $\Q = \bigcup_{i\ge1} \frac{1}{in}\Z$ the result will then be proved.

As in the proof of Theorem \ref{theorem:Z}, it is enough to show that
the 3-decks of $A \cap \frac{1}{in}\Z$ and $B\cap \frac{1}{in}\Z$, restricted to 
multisets of form $\set{0,k,\alpha}$, are equal. Now if  $a+\set{0,k,\alpha}
\subset A$ then $a\in X_A$, and so
\begin{eqnarray*}
a + \set{0,k,\alpha} \subset A \cap \frac{1}{in}\Z &\quad\iff\quad&
	a + \alpha \in \frac{1}{in}\Z \\
&\quad\iff\quad& \alpha \in \frac{1}{in}\Z.
\end{eqnarray*}
Thus the relevant parts of the 3-decks of $A\cap \frac{1}{in}\Z$ and $B\cap
\frac{1}{in}\Z$ are equal, and hence $A\cap \frac{1}{in}\Z = B\cap
\frac{1}{in}\Z$. 
\blot

\begin{theorem}\label{theorem:Qn}
Let $A\subset\Q^n$ be locally finite.  Then $A$ is reconstructible
from its 3-deck.
\end{theorem}

\proof Similar to the proof of Theorem \ref{theorem:Q}, with modifications as indicated in the proof of Theorem \ref{theorem:general}.
\blot

\begin{theorem}\label{theorem:R}
Let $A\subset\R$ be locally finite.  Then $A$ is reconstructible from
its 3-deck.
\end{theorem}

\proof Let $\{q:q\in I\}$ be a Hamel basis for $\R$ over $\Q$, where the set  
$I$ is
well-ordered by $\prec$.  This induces a total ordering on $\R$ by defining  
$ x < y$  iff $y-x =
\sum_{i=1}^n a_i q_i$ with $ q_1 \prec q_2 \prec \dots \prec q_n $ and $a_1 > 0$.
Given a subset $S\subset R$ we write $\< S>$ for the
collection of finite $\Q$-linear combinations of elements of $S$.

Now suppose that $A,B \subset \R$ 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=\set{a\in A:a+r\in
A}$, and $X_B = \setof{b\in B}{b+r \in B}$.
We may assume that $\min X_A = \min X_B=0$.  Let $I_0\subset I$ be a finite subset 
of $I$ such that
$x-y\in\< I_0>$ for all $x,y\in X_A \cup X_B$, and also $r \in \<I_0>$.   
Such a subset exists,
since $X_A \cup X_B$ is finite and every element of $\R$ can be written as a
$\Q$-linear combination of a finite set of elements from $I$.

We will show that for finite subsets $J$ with $I_0 \of J\of I$, the sets
$A \cap \< J>$ and $B \cap \< J>$ are equal, from
which it easily follows that $A=B$. Consider then such a $J$.
If $a + \set{0,r,\alpha} \subset A$ then $a \in X_A$ and
\begin{eqnarray*}
a + \set{0,r,\alpha} \subset A \cap \< J > &\quad\iff\quad&
	a + \alpha \in \< J > \\
&\quad\iff\quad& \alpha \in \< J > .
\end{eqnarray*}
Since $\<J>$ is isomorphic to $\Q^N$, for some $N$,  and, by the argument above,
the 3-decks of $A \cap \<J>$ and $B\cap\<J>$ restricted to multisets of form
$\set{0,r,\alpha}$ are the same, it follows
from Theorem \ref{theorem:Qn} that $A \cap \<J> = B\cap\<J>$.
Since $\bigcup_{J \contains I_0} \<J> = \R$, we have that
$A = B$.
\blot

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)=\lambda(x:X+x\subset S)$.  Call $S$ {\it locally finite} if $S(X)$ is finite 
whenever $|X|>1$.  We regard sets $X, Y$ as equivalent if $\lambda(X\bigtriangleup (Y+t))=0$ for some real number $t$.  Can we reconstruct every set of finite measure from its  
3-deck?
Can we reconstruct every locally finite set from its 3-deck?  Or from the $k$-deck for sufficiently large $k$?

\begin{thebibliography}{99}

\bibitem{AlCaKrRo} N. Alon, Y. Caro, I. Krasikov and Y. Roditty,
Combinatorial reconstruction problems, {\em J. Comb. Theory, Ser. B}
{\bf 47} (1989), 153--161

\bibitem{Bo} J. A. Bondy, A graph reconstructor's manual, {\em in}
Surveys in Combinatorics, 1991, ed. A.D. Keedwell, LMS Lecture Note
Series 166, 221--252

\bibitem{BoHe} J. A. Bondy and R. L. Hemminger, Graph reconstruction --
a survey, {\em J. Graph Theory} {\bf 1} (1977), 227--268

\bibitem{Ca} P. J. Cameron, Stories from the age of reconstruction,
Festschrift for C.~St.~J.~A.~Nash-Williams, {\em Congr. Numer.} {\bf
113} (1996), 31--41

\bibitem{Cab} 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 {\bf 165}, CUP, 1992, 340-351

\bibitem{KR} I.~Krasikov and Y.~Roddity, On a reconstruction problem for sequences,
{\em J. Comb. Theory, Ser. A} {\bf 77} (1977), 344-348

\bibitem{Mnuk} V. B. Mnukhin, The $k$-orbit reconstruction and the
orbit algebra, {\em Acta Appl. Math.} {\bf 29} (1992), 83--117

\bibitem{Mnukb} V. B. Mnukhin, The reconstruction of oriented necklaces, {\em J. Combinatorics, Information and System Sciences}, {\bf 20} (95), 261-272

\bibitem{Mnukc} V. B. Mnukhin, The $k$-orbit reconstruction for Abelian and Hamiltonian groups, {\em Acta Applicandae Mathematicae} {\bf 52} (98), 149-162

\bibitem{RSb} A. J. Radcliffe and A. D. Scott, Reconstruction subsets of ${\Z}_n$, J. Comb. Theory, Ser. A {\bf 83} (98), 169-187

\bibitem{RS} A. J. Radcliffe and A. D. Scott, Reconstructing subsets of
non-Abelian groups, manuscript.

\end{thebibliography}







\end{document}