On the determination of sets by their triple correlation in finite cyclic groups

Tamás Keleti^{∗}  Mihail N. Kolountzakis^{†}

31 March 2006

Abstract

Let G be a finite abelian group and E a subset of it. Suppose that we know for all subsets T of G of size up to k for how many x ∈ G the translate x + T is contained in E. This information is collectively called the k-deck of E. One can naturally extend the domain of definition of the k-deck to include functions on G. Given the group G when is the k-deck of a set in G sufficient to determine the set up to translation? The 2-deck is not sufficient (even when we allow for reflection of the set, which does not change the 2-deck) and the first interesting case is k = 3. We further restrict G to be cyclic and determine the values of n for which the 3-deck of a subset of ℤ_{n} is sufficient to determine the set up to translation. This completes the work begun by Grünbaum and Moore [GM] as far as the 3-deck is concerned. We additionally estimate from above the probability that for a random subset of ℤ_{n} there exists another subset, not a translate of the first, with the same 3-deck. We give an exponentially small upper bound when the previously known one was O(1/\sqrt{n}).

1 Introduction to the problem and results

Let G be a finite abelian group, written additively, and f : G → ℝ be a function. For k ≥ 2 we define the k-deck or k-th order correlation of f as the function

N_{f,k} : G^{k−1} → ℝ

defined by

N_{f,k}(x_{1}, …, x_{k−1}) = ∑_{x∈G} f(x)f(x + x_{1}) ⋯ f(x + x_{k−1}).  (1)

When E ⊆ G and f(x) = χ_{E}(x) is the indicator function of E we also write N_{E,k} in place of N_{f,k}. In this case, of f = χ_{E}, it is easy to see that the number N_{E,k}(x_{1}, x_{2}, …, x_{k−1}) is precisely the number of times the pattern

0, x_{1}, …, x_{k−1}

∗Department of Analysis, Eötvös Loránd University, Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary.

E-mail: elek@cs.elte.hu. Partially supported by OTKA grants 049786 and F 43620 and by European Commission IHP Network HARP (Harmonic Analysis and Related Problems), Contract Number: HPRN-CT-2001-00273 - HARP.

This research started when the first author visited the second author at the University of Crete and it continued while the first author was a visitor at the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Science.

†Department of Mathematics, Univ. of Crete, GR-71409 Iraklio, Greece. E-mail: kolount@gmail.com. Partially supported by European Commission IHP Network HARP (Harmonic Analysis and Related Problems), Contract Number: HPRN-CT-2001-00273 - HARP, and by grant INTAS 03-51-5070 (2004) (Analytical and Combinatorial Methods in Number Theory and Geometry). Also by the Greek research program ”Pythagoras 2” (75% European funds and 25% National funds).

can be translated by an arbitrary element of G to be contained in E. In particular N_{E,2} determines the difference multiset E −E of E. The k-deck may also be defined on an arbitrary locally compact abelian group, provided we replace the summation in the definition above with integration with respect to Haar measure.

As our primary interest is in indicator functions, we will mainly consider nonnegative functions f. Another reason for considering only real functions is to avoid the extra complication due to the fact that the functions f and ωf have the same k-deck whenever ω is a k-th root of unity.

It is evident that the functions f(x) and f_{t}(x) = f(x − t) have the same k-decks for all values of k. The problem we discuss in this paper is the following:

Is the function f : G → ℝ^{+} determined up to translation if we know its k-deck? What if the same question is asked for indicator functions?

It is not hard to see that for k = 2, and even for indicator functions, the answer is negative. Indeed, suppose that we have two sets A, B ⊆ G such that −B is not a translate of B and suppose also that the multisets E = A + B and F = A − B are actually sets. Take for example G = ℤ_{101} (the cyclic group of 101 elements), A = {0, 10, 20, 30} and B = {0, 1, 3}. Then it is easy to see that the sets E and F have the same 2-deck but are not necessarily translates of each other, e.g. in the example we mentioned.

In this paper we will restrict ourselves to finite cyclic groups and the emphasis will be on the 3-deck or triple correlation. This problem is of significance in several fields of applied science, for example crystallography and signal processing [Pet]. Another example is the method of speckle masking in atronomical imaging [LWW], where an averaged triple correlation of two-dimensional observation images taken in quick succession is inverted to obtain a sharper image. This process gets rid of interference due to slowly-varying inhomogeneities in the atmosphere and is apparently quite successful. For further applications see [JK] and the references therein.

Our problem is most naturally studied with the use of the Fourier Transform on G, defined for any function f : G → ℂ as a function f̂ on Γ, the group of characters of G (group homomorphisms into the multiplicative group {z ∈ ℂ : |z| = 1}), given by

f̂(γ) = ∑_{x∈G} f(x)\overline{γ(x)}.

In the particular case of interest to us when G = ℤ_{n} is the cyclic group of n elements then its dual group Γ is also isomorphic to ℤ_{n} and the FT of f : ℤ_{n} → ℂ is a function f̂: ℤ_{n} → ℂ given by

f̂(k) = ∑_{j=0}^{n−1} f(j)ζ_{n}^{−jk}, k = 0, …, n − 1,

where ζ_{n} = exp(2πi/n) is a primitive n-th root of unity.

It is easy to see that the Fourier Transform of the function N_{f,k} : G^{k−1} → ℝ^{+}, the function N̂_{f,k} : Γ^{k−1} → ℂ, is given by

N̂_{f,k}(ξ_{1}, …, ξ_{k−1}) = f̂(ξ_{1}) ⋯ f̂(ξ_{k−1})\overline{f̂(ξ_{1} + ⋯ + ξ_{k−1})}
= f̂(ξ_{1}) ⋯ f̂(ξ_{k−1})f̂(−(ξ_{1} + ⋯ + ξ_{k−1})) since f is real.  (2)

This implies that

N_{f,k} ≡ N_{g,k} ⟺ (ξ_{1} + … + ξ_{k} = 0 ⟹ f̂(ξ_{1}) ⋯ f̂(ξ_{k}) = ĝ(ξ_{1}) ⋯ ĝ(ξ_{k})) .  (3)

In particular, if N_{f,k} ≡ N_{g,k} for two nonnegative functions f and g on G, we immediately get f̂(0) = ĝ(0) by setting all ξ_{j} = 0. It is also clear that N_{f,k} ≡ N_{g,k} for nonnegative f and g implies N_{f,r} ≡ N_{g,r} for all 2 ≤ r ≤ k − 1 as well, so that identity of the k-decks implies the identity of all lower order r-decks. Choosing ξ_{1} = −ξ_{2} = ξ and ξ_{j} = 0 for j ≥ 3 we get |f̂(ξ)| = |ĝ(ξ)|. Note that

if k is odd then we get |f̂| ≡ \left|{ \atop g}\right| even for two arbitrary real functions f and g on G with N_{f,k} = N_{g,k}

if f̂(0) ≠ 0 or ĝ(0) ≠ 0. Furthermore, if k = 3 and if we know that f̂ has no zeros on Γ it follows using (2) that the ratio f̂/ĝ is a map from G to the unit circle which is a group homomorphism, and this is equivalent to the function f being a translate of the function g.

This reveals the fact that the main difficulty in the study of this problem is the existence of zeros in the Fourier Transform of the function whose k-deck we know. Consider for example the case of the group G = ℤ_{p}, p a prime. It is well known that the linear rank over ℚ of the set of p-th roots of unity is p − 1, and this implies that any non-trivial ℚ-linear combination of at most p − 1 such roots cannot vanish. In other words, if we have a non-constant function f : ℤ_{p} → ℚ (e.g. the indicator function of a non-trivial subset of ℤ_{p}), then its FT never vanishes on ℤ_{p} (which is the dual group of itself). By the previous discussion then the 3-deck of any function f : ℤ_{p} → ℚ determines f up to translation [RS1].

The question of whether N_{f,k} determines f up to translation depends both on the group G on which f is defined as well as on assumed properties of f. The main cases of interest are when (a) f is any nonnegative function, (b) f is a rational-valued function, possibly restricted to be nonnegative, and (c) f is an indicator function. It is not hard to see, for instance, that on the group ℝ there are, for every k, nonnegative functions which are not determined up to translation from their k-deck [JK]. The same question is open if one demands that f is an indicator function of set of finite measure although the answer is known to be positive in certain special cases of sets [JK]. On the other hand even the 3-deck determines a function f ∈ L^{1}(ℝ) if it is of compact support [JK].

1.1 Previous results

In the case of cyclic groups the most significant work is that of Grünbaum and Moore [GM]. This work seems largely to have gone unnoticed in the mathematical literature although it solves the most important cases of the problem for cyclic groups. This is probably due to the fact that it was published in a Crystallography journal. The following is a summary of the results in [GM] regarding reconstructing f on ℤ_{n} from its k-deck. Notice that in [GM] it is assumed at the outset that all functions to be reconstructed from their k-deck have a non-zero sum over the group.

1. For any n, if f and g are rational-valued functions on ℤ_{n} with the same 6-deck then they are translates of each other [GM, Theorem 4].

2. If n is even and at least 30 then there are sets E, F ⊆ ℤ_{n} which have the same 3-deck but are not translates of each other [GM, §5.3].

3. If n is odd, f and g are rational-valued functions on ℤ_{n} with the same 3-deck and f̂(1) ≠ 0 then f and g are translates of each other [GM, Theorem 3]. This is heavily based on a result of Lenstra [L] (see our §2.1).

4. For any n suppose that f is a rational-valued function on ℤ_{n} and E ⊆ ℤ_{n}, g = χ_{E}. Then if f and g have the same 4-deck and f̂(1) ≠ 0 it follows that f and g are translates of each other [GM, Theorem 5]. It is suggested in [GM] that the condition f̂(1) ≠ 0 may be unnecessary.

5. There is no value of k such that for all n the equality of the k-deck of two real functions f and g on ℤ_{n} implies that they are translates of each other [GM, §8.2].

6. If n = pqr, with p and q distinct primes, and r > 1 is an integer then there are two rationalvalued functions f and g on ℤ_{n} which have the same 3-deck, satisfy f̂(1) = ĝ(1) = 0, and are not translates of each other [GM, §5.2].

Radcliffe and Scott [RS2] study the problem for infinite subsets of ℝ which are subject to some sort of “local finiteness” and prove reconstructibility from the 3-deck. In [RS1] the same authors prove reconstructibility up to translation from the 3-deck in ℤ_{p}, p a prime, show that almost all subsets of ℤ_{n} are determined up to translation by their 3-deck and show that any set in ℤ_{n} is determined up to translation by its k-deck with k being 9 times the number of distinct prime factors of n.

Pebody, Radcliffe and Scott [PRS] study a variation of the problem. They prove that any finite subset E of the plane can be reconstructed up to rigid motion if one knows for any subset A of the plane of up to 18 points how many rigid-motion copies of A are to be found in E.

Jaming and Kolountzakis [JK] study the problem both in the case of the group ℝ and in cyclic groups. In the case of ℝ it is pointed out that several conditions which guarantee some sort of analyticity of f̂ are enough to imply that the 3-deck of f determines f up to translation. It is shown that for every k there exist two nonnegative, smooth f, g ∈ L^{1}(ℝ) with the same k-deck, which are not translates of each other. In fact for some such f there exist even uncountably many, translation inequivalent, functions g which have the same k-deck as f.

It is also proved in [JK] that if E ⊆ ℝ has finite measure, g ∈ L^{1}(ℝ) is nonnegative and χ_{E} and g have the same 3-deck, then g is itself an indicator function. Although it is still an open problem whether any E ⊆ ℝ of finite measure is determined up to translation from its 3-deck, it is proved in [JK] that if E is an open set with gaps bounded below (write E as a disjoint collection of open intervals and look at the gaps so defined) then E is determined from its 3-deck.

In the case of the cyclic group ℤ_{n} it is proved in [JK, Theorem 3.1 and following Remark] that when n = p^{α}, p a prime larger than 2, then the 3-deck of a set in ℤ_{n} determines the set up to translation. It is also shown that if n = 2^{α} then the 4-deck of a set determines the set up to translation (and this is mistakenly attributed to [GM]). In [JK, Theorem 3.2] it is erroneously claimed that if n = pq with p and q two distinct primes then the 3-deck is enough to reconstruct a set in ℤ_{n}. Given the results of [GM] summarized above, the condition p, q > 2 clearly needs to be added and then the theorem is correct. A corrected proof is given in our §2. The attempt, at the end of [JK], to explain the examples given by Grünbaum and Moore for the case n = pqr (see summary above) is also erroneous.

Pebody [P] defines r(G) (resp. rset(G)) the minimum k such that the k-deck of a nonnegative rational-valued function on G (resp. subset of G) determines the function (resp. set) up to translation. Improving results for the cyclic group of Alon, Caro, Krasikov and Roditty [ACKR] and Radcliffe and Scott [RS1], Pebody, computes the number r(G) for all finite abelian G and his result implies r(ℤ_{n}) ≤ 6. For the cyclic groups the result had already been proved in [GM]. In particular, Pebody gets that the 3-deck determines all nonnegative rational valued functions up to translation on the cyclic group ℤ_{n} (n ≥ 3) if and only if n is a power of an odd prime or the product of two odd primes.

1.2 New results

In §2 we complete the characterization of those finite cyclic groups in which the 3-deck determines any subset up to translation. We show that 1. If n = p^{2}q, with p and q distinct odd primes then any subset of ℤ_{n} can be determined up to

translation from its 3-deck (Theorem 2.1).

2. The same is true if n = pqr, with p, q, r distinct odd primes (Theorem 2.1).

3. If n = pqrd, with p, q distinct primes and r, d > 1, then there are two subsets E and F of ℤ_{n} with the same 3-deck which are not translates of each other (Theorem 2.23).

4. If n = 2k, k ≥ 6, we give two subsets E and F of ℤ_{n}, not translates of each other, which have the same 3-deck (Theorem 2.22). This result subsumes the above mentioned result of [GM] (for even n, n ≥ 30) and, we think, our examples are much easier to understand.

If n is even and at most 10 we show that there are no such examples (Proposition 2.21).

Thus we get the following.

Corollary 1.1. Every subset of the cyclic group ℤ_{n} can be determined up to translation from its 3deck if and only if n is a power of an odd prime or n is the product of at most three (not necessarily distinct) odd primes or n ∈ {2, 4, 6, 8, 10}.

Remark 1.2. As we were finishing this paper we came across a manuscript by Pebody [P2] where the cases of odd n for which the 3-deck is sufficient are also determined. Our work was done independently and, apparently, almost simultaneously.

Comparing Corollary 1.1 to the last mentioned special case of the result of Pebody [P] in the previous subsection, we observe that the analogous characterization of the “good” values of n is different if we consider nonnegative rational valued functions instead of subsets.

Key to our results are theorems which significantly restrict the zero set of the Fourier Transform of indicator functions of subsets of certain cyclic groups. See for instance Lemma 2.18.

In §3 we study the number of subsets of ℤ_{n} which are not determined by their 3-deck up to translation. In [RS1] Radcliffe and Scott had already shown that this number is O(2^{n}/\sqrt{n}) as n → ∞. We show that this number is in fact much smaller, namely O(2^{−C_{ϵ}n^{1−ϵ}}2^{n}), for any fixed ϵ > 0 (Theorem 3.4).

2 For which cyclic groups the 3-deck determines a set up to translation

2.1 Positive results

The main result of this subsection is the following:

Theorem 2.1. Let n be a power of an odd prime or the product of at most three (not necessarily distinct) odd primes. Then every subset of ℤ_{n} is uniquely determined up to translation by its 3-deck.

For completeness and because it needs no extra effort, our proof will cover not only the new results but also the known ones. We shall use only the same theorem of H. W. Lenstra that was used by Grünbaum and Moore in [GM]:

Lenstra’s Theorem [L]. If N is an odd integer, and m and N are coprime then there exists a finite sequence x_{1}, …, x_{l} of relative primes to N such that x_{1} = 1, x_{l} = m and every member except the first is the sum or difference of two not necessarily different previous members of the sequence.

As we saw in the Introduction, the 3-deck determines a nonnegative function up to translation if its Fourier Transform has no zero. We shall show that if n is a power of an odd prime or n is the product of at most three (not necessarily distinct) odd primes then the support of the Fourier Transform of a characteristic function on ℤ_{n} is always rich enough to get the same conclusion. Our method can be considered as a generalization of the methods in [GM] and [JK].

The concept of extendable domain, defined below, is central to the problem and the techniques of this paper. In fact, this is the right notion for what we called “rich enough” in the previous paragraph.

Definition 2.2. We say that A ⊂ ℤ_{n} is an extendable domain if for every h : A → ℝ/ℤ additive (by which we mean that h(x + y) = h(x) + h(y) whenever x, y, x + y ∈ A) function there exists an L ∈ ℝ such that h(k) = Lk (mod 1) for every k ∈ A.

Reconstructing f (up to translation) from its 3-deck is simple if supp f̂is an extendable domain.

Lemma 2.3. (1) If f and g are nonnegative functions on ℤ_{n} with the same 3-deck and supp f̂ is an extendable domain then f and g are translates of each other.

(2) If f and g are real valued functions on ℤ_{n} with the same 3-deck, f̂(0) ≠ 0 or ĝ(0) ≠ 0 and supp f̂ is an extendable domain then f and g are translates of each other.

Proof. Suppose that f and g satisfy the conditions of (1) or (2). We saw in the Introduction that in these cases having the same 3-deck implies that f̂ and ĝ have the same modulus. Hence there exists a function h : supp f̂ → ℝ/ℤ such that ĝ(l) = e^{2πih(l)}f̂(l). Substituting this to (3) we get that h must be additive as defined in Definition 2.2. Then, since supp f̂ is an extendable domain, h must be linear, thus e^{2πih(l)} is the restriction of a character to supp f̂, and so f and g are translates of each other.

Therefore, to prove Theorem 2.1 it is enough to prove the following:

Proposition 2.4. If n is a power of an odd prime or n is the product of at most three (not necessarily distinct) odd primes then the support of the Fourier Transform of a characteristic function on ℤ_{n} is always an extendable domain.

To prove this proposition we need several facts and lemmas, some of which may be known and/or interesting in themselves. The following five facts are surely known but for completeness, and because it is easier to prove them than to find them in the literature, we present their proofs.

Notation 2.5. Let (k, l) denote the greatest common divisor of k and l. For a|n let

⟨a⟩_{n} = {k ∈ ℤ_{n} : (k, n) = a} and

aℤ_{n} = \{0, a, 2a, …, (\frac{n}{a} − 1) a \} ⊂ ℤ_{n}.

Fact 2.6. If f : ℤ_{n} → ℚ then supp f̂ is the union of sets of the form ⟨a⟩_{n} for some a|n.

Proof. We can write f̂(k) = ∑_{j=0}^{n−1} f(j)ζ_{n,k}^{j}, where ζ_{n,k} = e^{−2πik/n} is the k-th root of unity of order n. The right hand side is a rational polynomial evaluated at the roots of unity. It is well known that ζ_{n,k} is an algebraic conjugate of ζ_{n,l} over ℚ if and only if (n, k) = (n, l).

Fact 2.7. For a|n a function f : ℤ_{n} → ℂ is a-periodic if and only if supp f̂ ⊂ \frac{n}{a}ℤ_{n}.

Proof. The space of a-periodic functions on ℤ_{n} has dimension a and it is clearly spanned by the characters χ_{l}(j) = e^{2πi \frac{ln}{a} j}, l = 0, 1, …, a − 1.

Fact 2.8. For a function f : ℤ_{n} → ℂ we have supp f̂ ⊂ a_{1}ℤ_{n} ∪ … ∪ a_{k}ℤ_{n} if and only if f can be written in the form f = f_{1} + … + f_{k}, where f_{j} : ℤ_{n} → ℂ is \frac{n}{a_{j}} -periodic (j = 1, …, k).

Proof. The splitting f = ∑ f_{j} is accomplished by arbitrarily splitting f̂ = ∑ f̂_{j}, in a way that f̂_{j} is supported on a_{j}ℤ_{n}, inverting the Fourier Transform and using Fact 2.7.

Fact 2.9. If n is odd then any integer k can be written as k = a + b where (a, n) = (b, n) = 1.

Proof. We can clearly assume that n is squarefree; that is, it is of the form n = p_{1} ⋯ p_{r}, where p_{1}, …, p_{r} are distinct primes. For each j = 1, …, r let a_{j} = 2 and b_{j} = −1 if k = 1 (mod p_{j}) and let a_{j} = 1 and b_{j} = k − 1 otherwise. By the Chinese Remainder theorem there exist a and b such that a = a_{j} (mod p_{j}) and b = b_{j} (mod p_{j}) for j = 1, …, r. Now a + b = k (mod p_{j}) for each j = 1, …, r, so a + b = k (mod n). By choosing a properly, by which we mean that we add a multiple of n to a if necessary, we can guarantee that a + b = k. Since each p_{j} > 2, we have a_{j}, b_{j} ≠ 0 (mod p_{j}), so (a, n) = (b, n) = 1.

Fact 2.10. If there are two equivalence relations on a set such that both contain at least two classes then there exist two elements which are inequivalent w.r.t. both relations.

Proof. If not then any two elements which are inequivalent w.r.t. the first relation should be equivalent w.r.t. the second. This easily implies that there is only one equivalence class w.r.t. the second relation, a contradiction.

The following will be used repeatedly in the sequel.

Lemma 2.11. If a is a divisor of the odd n and ⟨a⟩_{n} ⊂ A ⊂ aℤ_{n} then A is an extendable domain.

Proof. Let h : A → ℝ/ℤ be an additive function. It is enough to prove that

m ∈ ℤ, ma ∈ A ⟹ h(ma) = mh(a) (mod 1),  (4)

since then for any L ∈ ℝ such that h(a) = La (mod 1) we get that h(ma) = mh(a) = Lma (mod 1), which is exactly what we want to show.

Let N = n/a. Note that ma ∈ ⟨a⟩_{n} holds if and only if m and N are coprime. Using the previously stated Lenstra’s Theorem for N = n/a and an m such that m and N are coprime we get a sequence x_{1}, …, x_{l} of relative primes to N such that x_{1} = 1, x_{l} = m and every member except the first is the sum or difference of two not necessarily different previous members of the sequence. Note that, since x_{i} and n/a are coprime, x_{i}a ∈ ⟨a⟩_{n} ⊂ A for each i. Then by induction we get that h(x_{i}a) = x_{i}h(a), and so (4) holds whenever m and n/a are coprime. Then (4) in the general case follows by using Fact 2.9.

Corollary 2.12. If n is odd, f : ℤ_{n} → ℚ and a ∈ supp f̂ ⊂ aℤ_{n} then supp f̂ is an extendable domain.

In particular, the following two statements hold:

(i) If n is odd, f : ℤ_{n} → ℚ and f̂(1) ≠ 0 then supp f̂ is an extendable domain.

(ii) If n is a power of an odd prime and f : ℤ_{n} → ℚ then supp f̂ is an extendable domain.

Proof. The first statement follows immediately from Lemma 2.11 and Fact 2.6. If a = 1 then we get (i). Statement (ii) is also a special case of the first statement since if n = p^{k} and l is minimal such that p^{l} ∈ supp f̂ then p^{l} ∈ supp f̂ ⊂ p^{l}ℤ_{n}. □

The next lemma shows that the sum of two periodic functions with coprime periods cannot have too small a range.

Lemma 2.13. If χ_{E} = f_{a} + f_{b}, and f_{a} and f_{b} are periodic ℤ → ℂ functions with coprime periods a and b then χ_{E} is periodic with period a or b.

Proof. Using the periodicity and χ_{E} = f_{a} + f_{b}, for any k, n, l ∈ ℕ we get

f_{b}(ak + bn + l) = f_{b}(ak + l) = χ_{E}(ak + l) − f_{a}(ak + l) = χ_{E}(ak + l) − f_{a}(l).  (5)

Since a and b are coprime, for any fixed l ∈ ℤ every integer can be written in the form ak + bn + l. Thus (5) implies that for any fixed l ∈ ℤ the range of f_{b} is a subset of R_{l} = {−f_{a}(l), 1 − f_{a}(l)}, as witnessed by the right hand side of (5).

If f_{b} is a constant function then we have the desired conclusion as χ_{E} is then a-periodic. If f_{b} is not a constant then the range of f_{b} is equal to the set R_{l}, for any integer l, and this implies that R_{l} is independent of l, or, in other words, that f_{a} is a constant. In that case χ_{E} is b-periodic.

Lemma 2.14. Suppose that a and b are divisors of n, n/a and n/b are coprime, E ⊂ ℤ_{n}, and supp χ̂_{E} ⊂ aℤ_{n} ∪ bℤ_{n}. Then supp χ̂_{E} ⊂ aℤ_{n} or supp χ̂_{E} ⊂ bℤ_{n}.

Proof. By Fact 2.8, supp χ̂_{E} ⊂ aℤ_{n} ∪ bℤ_{n} implies the existence of an n/a-periodic function f and an n/b periodic function g such that χ_{E} = f + g. Since n/a and n/b are coprime, by Lemma 2.13, we get that χ_{E} must be n/a-periodic or n/b periodic. By Fact 2.7, this implies that supp χ̂_{E} ⊂ aℤ_{n} or supp χ̂_{E} ⊂ bℤ_{n}.

Lemma 2.15. Suppose that a and b are coprime divisors of n, E ⊂ ℤ_{n},

supp χ̂_{E} ⊂ (aℤ_{n} ∪ bℤ_{n} \ abℤ_{n}) ∪ {0}.

Then supp χ̂_{E} ⊂ aℤ_{n} or supp χ̂_{E} ⊂ bℤ_{n}.

Proof. Let c = \frac{n}{ab}. By Fact 2.8, supp χ̂_{E} ⊂ aℤ_{n} ∪ bℤ_{n} implies that χ_{E} can be written in the form χ_{E} = f_{a} + f_{b}, where f_{a} is bc-periodic and f_{b} is ac-periodic. Applying Lemma 2.13 we get that for each t = 0, 1, …, c − 1 the function χ_{E}(kc + t) is a-periodic or b-periodic. Let m_{t} be the number of points of the form kc + t in E. Then

m_{t} ∈ {0, 1, …, ab} is divisible by a or b;

by a if χ_{E}(kc + t) is b-periodic and by b if χ_{E}(kc + t) is a-periodic. (6)

A straightforward calculation shows that for any s ∈ ℤ

χ̂_{E}(sab) = ∑_{t=0}^{c−1} m_{t} (e^{\frac{2πis}{c}} )^{t} .

Since we assumed that χ̂_{E}(sab) = 0 for s = 1, …, c−1, we get that the c−1 c-th roots of unity e^{\frac{2πis}{c}} (s = 1, …, c−1) are all roots of the (c−1)-th order polynomial ∑_{t=0}^{c−1} m_{t}z^{t}. Hence ∑_{t=0}^{c−1} m_{t}z^{t} must be a constant multiple of Π_{s=1}^{c−1}(z − e^{\frac{2πis}{c}}) = ∑_{t=0}^{c−1} z^{t} and so all m_{t} must be the same. Using (6) and that a and b are coprime this implies that χ_{E}(kc + t) is a-periodic for each t or b-periodic for each t. Thus χ_{E} is ac-periodic or bc-periodic hence, by Fact 2.7, supp χ̂_{E} ⊂ aℤ_{n} or supp χ̂_{E} ⊂ bℤ_{n}.

Lemma 2.16. If a and b are coprime divisors of the odd n and ⟨a⟩_{n} ∪ ⟨b⟩_{n} ∪ {ab} ⊂ A ⊂ aℤ_{n} ∪ bℤ_{n} then A is an extendable domain.

Proof. Let h : A → ℝ/ℤ be an additive function. We have to find an L ∈ ℝ such that h(k) = Lk (mod 1) for every k ∈ A.

By Lemma 2.11, A ∩ aℤ_{n} and A ∩ bℤ_{n} are extendable domains, so there exist L_{a} and L_{b} such that

h(k) = L_{a}k (mod 1) if k ∈ A ∩ aℤ_{n},  and  h(k) = L_{b}k (mod 1) if k ∈ A ∩ bℤ_{n}. (7)

Note that for any u, v ∈ ℤ, L_{a} can be replaced by L_{a} + \frac{u}{a} and L_{b} can be replaced by L_{b} + \frac{v}{b} in (7). Thus it is enough to find u, v ∈ ℤ such that L_{a} + \frac{u}{a} = L_{b} + \frac{v}{b}, which is equivalent to

ub − va = L_{a}ab − L_{b}ab.  (8)

Using ab ∈ A and (7), we get L_{a}ab = h(ab) = L_{b}ab (mod 1), so L_{a}ab − L_{b}ab ∈ ℤ. Then, since a and b are coprime, there exists u, v ∈ ℤ for which (8) holds, which completes the proof.

In the sequel we shall use Fact 2.6 in the proofs many times without explicitly citing it.

Lemma 2.17. Let the odd n = pqd, where p and q are two distinct primes, and d is a prime or d = 1. If E ⊂ ℤ_{n} and supp χ̂_{E} ⊂ pℤ_{n} ∪ qℤ_{n} then supp χ̂_{E} is an extendable domain.

Proof. If p, q ∈ supp χ̂_{E} then, applying Lemma 2.15 for a = p, b = q, we get that supp χ̂_{E} ∩ pqℤ_{n} ≠ {0}, which implies that pq ∈ supp χ̂_{E}. Then we can apply Lemma 2.16 to get that supp χ̂_{E} is indeed an extendable domain.

So we can suppose by symmetry that q ∉ supp χ̂_{E}. Then supp χ̂_{E} ⊂ pℤ_{n} ∪ qℤ_{n} implies that supp χ̂_{E} ⊂ pℤ_{n} ∪ qdℤ_{n}. Then, in case of d ≠ p by Lemma 2.14, in case of d = p clearly, we have supp χ̂_{E} ⊂ pℤ_{n} or supp χ̂_{E} ⊂ qdℤ_{n}.

If supp χ̂_{E} ⊂ qdℤ_{n} then supp χ̂_{E} = ⟨qd⟩_{n}∪{0} or supp χ̂_{E} = {0}, so we are done by Lemma 2.11. So we can suppose that {0} ≠ supp χ̂_{E} ⊂ pℤ_{n}. If p ∈ supp χ̂_{E} then by Corollary 2.12 supp χ̂_{E}

is an extendable domain, so we can suppose that p ∉ supp χ̂_{E}. Then, by Fact 2.6, supp χ̂_{E} can be only ⟨pd⟩_{n} ∪ {0} or ⟨pq⟩_{n} ∪ {0} or ⟨pq⟩_{n} ∪ ⟨pd⟩_{n} ∪ {0} with d ≠ 1, q. The last case is impossible by Lemma 2.14 (for a = pq, b = pd), while in the first two cases Lemma 2.11 implies that supp χ̂_{E} is an extendable domain.

The following lemma about the possible support of the Fourier Transform of characteristic functions on ℤ_{n} is the key for handling the hardest case when n is the product of three distinct primes. This statement might be useful in other applications, too.

Lemma 2.18. Suppose p, q and r are pairwise coprime, but not necessarily primes. Let n = pqr and let E ⊂ ℤ_{n}. Then

p, q ∈ supp χ̂_{E} ⊂ pℤ_{n} ∪ qℤ_{n} ∪ rℤ_{n} ⟹ (∃z ∈ {1, 2, …, r − 1}) zpq ∈ supp χ̂_{E}.

Proof. Suppose that for each z = 1, 2, …, r − 1 we have

0 = χ̂_{E}(zpq) = ∑_{c=0}^{r−1} ∑_{k=0}^{pq−1} χ_{E}(kr + c)e^{−2πi \frac{(kr+c)zpq}{pqr}} = ∑_{c=0}^{r−1} ( ∑_{k=0}^{pq−1} χ_{E}(kr + c)) (e^{−2πi \frac{z}{r}} )^{c} .

This implies that ∑_{k=0}^{pq−1} χ_{E}(kr + c) must be the same for each c ∈ ℤ_{r}; that is,

∑_{k=0}^{pq−1} χ_{E}(kr + c_{1}) − χ_{E}(kr + c_{2}) = 0  (c_{1}, c_{2} ∈ ℤ_{r}).  (9)

For each j ∈ ℤ_{n} (n = pqr) let (a_{j}, b_{j}, c_{j}) ∈ ℤ_{p} × ℤ_{q} × ℤ_{r} be the unique triple such that

j = a_{j} mod p, j = b_{j} mod q and j = c_{j} mod r,

and let ϕ be the inverse of the above ℤ_{n} → ℤ_{p} × ℤ_{q} × ℤ_{r} bijections; that is, ϕ(a, b, c) (a ∈ ℤ_{p}, b ∈ ℤ_{q}, c ∈ ℤ_{r}) is the unique element of ℤ_{n} for which

ϕ(a, b, c) = a mod p, ϕ(a, b, c) = b mod q and ϕ(a, b, c) = c mod r.

Since supp χ̂_{E} ⊂ pℤ_{n} ∪ qℤ_{n} ∪ rℤ_{n}, χ_{E} can be written as χ_{E} = f + g + h, where f is qr-periodic, g is pr periodic and h is pq-periodic.

Since f is qr-periodic, f(ϕ(a, b, c)) does not depend on a, so f ∘ ϕ can be written in the form f(ϕ(a, b, c)) = F (b, c). Similarly g ∘ ϕ and h ∘ ϕ can be written as g(ϕ(a, b, c)) = G(a, c) and h(ϕ(a, b, c)) = H(a, b). So using the notation E′ = ϕ^{−1}(E) ⊂ ℤ_{p} × ℤ_{q} × ℤ_{r} we get that

χ_{E′}(a, b, c) = F (b, c) + G(a, c) + H(a, b) a ∈ ℤ_{p}, b ∈ ℤ_{q}, c ∈ ℤ_{r}.

We claim that there exist c_{1}, c_{2} ∈ ℤ_{r} such that neither the ℤ_{q} → ℝ function F (· , c_{1}) − F (· , c_{2}), nor the ℤ_{p} → ℝ function G(· , c_{1}) − G(· , c_{2}) is constant. Indeed, F (· , c_{1}) − F (· , c_{2}) being constant defines an equivalence relation on ℤ_{r} and so does G(· , c_{1}) − G(· , c_{2}) being constant. If there is only one equivalence class w.r.t. the first relation then F can be written as F (b, c) = u(b) + v(c) which implies

χ_{E}(j) = χ_{E′}(a_{j}, b_{j}, c_{j}) = v(c_{j}) + G(a_{j}, c_{j}) + u(b_{j}) + H(a_{j}, b_{j}),

and this would in turn imply χ̂_{E}(p) = 0, contradicting our assumption. Hence there are at least two classes w.r.t. the first relation. Similarly there are two classes w.r.t. the second relation and using Fact 2.10 we obtain our claim.

On the other hand, since

(F (b, c_{1}) − F (b, c_{2})) + (G(a, c_{1}) − G(a, c_{2})) = χ_{E′}(a, b, c_{1}) − χ_{E′}(a, b, c_{2}) ∈ {−1, 0, 1}

for any a ∈ ℤ_{p}, b ∈ ℤ_{q}, we have

Range(F (· , c_{1}) − F (· , c_{2})) + Range(G(· , c_{1}) − G(· , c_{2})) ⊂ {−1, 0, 1}.

Since by the previous paragraph Range(F (· , c_{1}) − F (· c_{2})) and Range(G(· , c_{1}) − G(· , c_{2})) have at least two elements, this implies that they must be of the form

Range(F (· , c_{1}) − F (· , c_{2})) = {A, A + 1},
Range(G(· , c_{1}) − G(· , c_{2})) = {−A, −A − 1}

for some A ∈ ℝ.

Let l_{1} ∈ {1, …, q − 1} be the number of elements b ∈ ℤ_{q} for which F (b, c_{1}) − F (b, c_{2})) = A and l_{2} ∈ {1, …, p − 1} be the number of elements a ∈ ℤ_{p} for which G(a, c_{1}) − G(a, c_{2})) = −A.

Then, combining this with (9) we get

0 = ∑_{k=0}^{pq−1} χ_{E}(kr + c_{1}) − χ_{E}(kr + c_{2})
= ∑_{a∈ℤ_{p}} ∑_{b∈ℤ_{q}} χ_{E′}(a, b, c_{1}) − χ_{E′}(a, b, c_{2})
= ∑_{a∈ℤ_{p}} ∑_{b∈ℤ_{q}} F (b, c_{1}) − F (b, c_{2}) + G(a, c_{1}) − G(a, c_{2})
= pl_{1}A + p(q − l_{1})(A + 1) + ql_{2}(−A) + q(p − l_{2})(−A − 1)
= −l_{1}p + l_{2}q,

which is a contradiction since l_{1}p cannot be divisible by q.

Lemma 2.19. Let n = pqr with p, q, r three distinct primes, E ⊂ ℤ_{n}. Then

p, q, r ∈ supp χ̂_{E} ⊂ pℤ_{n} ∪ qℤ_{n} ∪ rℤ_{n} ⟹ supp χ̂_{E} = pℤ_{n} ∪ qℤ_{n} ∪ rℤ_{n}.

Proof. Suppose that p, q, r ∈ supp χ̂_{E} ⊂ pℤ_{n} ∪ qℤ_{n} ∪ rℤ_{n}. By Lemma 2.18 we have ⟨pq⟩_{n} ∪ ⟨pr⟩_{n} ∪ ⟨qr⟩_{n} ⊂ supp χ̂_{E}. Since E cannot be empty, ⟨pqr⟩_{n} ⊂ supp χ̂_{E}. Since pℤ_{n} ∪ qℤ_{n} ∪ qℤ_{n} = ⟨p⟩_{n} ∪ ⟨q⟩_{n} ∪ ⟨r⟩_{n} ∪ ⟨pq⟩_{n} ∪ ⟨pr⟩_{n} ∪ ⟨qr⟩_{n} ∪ ⟨pqr⟩_{n}, this completes the proof.

Lemma 2.20. If a, b, c ∈ ℤ are pairwise coprime then aℤ_{n} ∪ bℤ_{n} ∪ cℤ_{n} is an extendable domain.

Proof. Let A = aℤ_{n} ∪ bℤ_{n} ∪ cℤ_{n} and let h : A → ℝ/ℤ be additive. Then it is easy to show that for α = h(a)/a, β = h(b)/b, γ = h(c)/c we have

h(ma) = αma, h(mb) = βmb, h(mc) = γmc (mod 1) (m ∈ ℤ).  (10)

It is enough to find u, v, w ∈ ℤ such that

α + \frac{u}{a} = β + \frac{v}{b} = γ + \frac{w}{c}  (11)

since then h(x) = Lx (mod 1) would follow for L = α + \frac{u}{a} = β + \frac{v}{b} = γ + \frac{w}{c} from (10). For v ∈ ℤ there exist u and w such that (11) holds if

va = αab − βab (mod b) and vc = γbc − βbc (mod b),

which hold for some v ∈ ℤ if and only if

αab − βab ∈ ℤ, γbc − βbc ∈ ℤ and c(αab − βab) = a(γbc − βbc) (mod b).  (12)

Using (10) for m = a, b, c we get that

αab = βab,  βbc = γbc and αac = βac  (mod 1),

which implies (12) and so completes the proof.

Proof. (Proposition 2.4) By Corollary 2.12 we are done if n is a power of an odd prime or if 1 ∈ supp χ̂_{E}. So we can suppose that 1 ∉ supp χ̂_{E} and n = pqr, where p and q are different primes and r is a prime or r = 1. If r = 1 or r = p or r = q then n equals pq or p^{2}q or pq^{2} and so 1 ∉ supp χ̂_{E} implies that supp χ̂_{E} ⊂ pℤ_{n} ∪ qℤ_{n}, hence we are done by Lemma 2.17.

Therefore we can suppose that 1 ∉ supp χ̂_{E} and n = pqr, where p, q and r are distinct primes. Then we have supp χ̂_{E} ⊂ pℤ_{n} ∪ qℤ_{n} ∪ rℤ_{n}.

If p, q, r ∈ supp χ̂_{E} then, by Lemma 2.19, we have supp χ̂_{E} = pℤ_{n} ∪ qℤ_{n} ∪ rℤ_{n}, which is an extendable domain by Lemma 2.20.

Otherwise, we can suppose by symmetry that r ∉ supp χ̂_{E} and so supp χ̂_{E} ⊂ pℤ_{n} ∪ qℤ_{n}. Then we are done by Lemma 2.17

This completes the proof of Proposition 2.4 and so also the proof of Theorem 2.1.

If n is even then we get positive results for small n:

Proposition 2.21. For n = 2, 4, 6, 8 and 10 every subset of ℤ_{n} is uniquely determined up to translations by its 3-deck.

For n = 2, 4 and 6 this statement follows very easily from the definition of 3-deck. For both n = 8 and n = 10 one can provide proofs using the lemmas and the method of this section. However, in these cases there are only 2^{8} and 2^{10} subsets of ℤ_{n}, so one can easily check (and we indeed did check) the statement by computer. Hence we omit the quite complicated detailed proof, in which many cases have to be distinguished and no new idea is needed.

2.2 Negative results

Theorem 2.22. Let n = 2k with k ≥ 6 integer. Then there exists E, F ⊂ ℤ_{n} such that they are not translates of each other, however they have the same 3-deck.

Proof. Let

E = {0} ∪ {3, 4, …, k − 1} ∪ {k + 1, k + 2}, and F = {0, 1} ∪ {3, 4, …, k − 1} ∪ {k + 2}.

Since k ≥ 6, both E and F contain a unique block of k − 3 consecutive numbers. Thus if a translation takes E to F then this block of E must be taken to the block of F. Since these blocks are identical, the translation must be the identity. But E ≠ F, so we proved that they are not the translates of each other.

By (2), for checking that E and F have the same 3-deck we have to show that for the Fourier Transforms of their characteristic function we have

s_{1} + s_{2} + s_{3} = 0 (mod 2k) ⟹ χ̂_{E}(s_{1})χ̂_{E}(s_{2})χ̂_{E}(s_{3}) = χ̂_{F} (s_{1})χ̂_{F} (s_{2})χ̂_{F} (s_{3}).  (13)

Letting z = ζ_{2k}^{−s} = e^{−2πi \frac{s}{2k}} we have

χ̂_{E}(s) = ζ_{2k}^{−0s} + (ζ_{2k}^{−3s} + ζ_{2k}^{−4s} + … + ζ_{2k}^{−(k−1)s}) + ζ_{2k}^{−(k+1)s} + ζ_{2k}^{−(k+2)s}  (14)
= 1 + (z^{3} + z^{4} + … + z^{k−1}) + z^{k+1} + z^{k+2} = (1 − z + z^{3})(1 + z + … + z^{k−1}),

and similarly

χ̂_{F} (s) = 1 + z + (z^{3} + z^{4} + … + z^{k−1}) + z^{k+2} = (1 − z^{2} + z^{3})(1 + z + … + z^{k−1}). (15)

If s is even but s ≠ 0 (mod 2k) then

1 + z + … + z^{k−1} = \frac{z^{k} − 1}{z − 1} = \frac{e^{−2πi \frac{ks}{2k}} − 1}{e^{−2πi \frac{s}{2k}} − 1} = 0,

and so χ̂_{E}(s) = χ̂_{F} (s) = 0.

Since s_{1} + s_{2} + s_{3} = 0 (mod 2k) implies that at least one of s_{1}, s_{2} and s_{3} is even, we get that (13) clearly holds unless at least one of s_{1}, s_{2} and s_{3} is zero.

So suppose that at least one of s_{1}, s_{2} and s_{3} is zero. Then, in order to check (13), we have to show that

χ̂_{E}(s)χ̂_{E}(−s) = χ̂_{F} (s)χ̂_{F} (−s)  (s ∈ ℤ_{2k}).  (16)

This is just a restatement of the fact that E and F have the same 2-deck, which is clearly true as E is a translate of −F.

Theorem 2.23. Let n = pqrd with p, q two distinct primes and r, d > 1 integers. Then there exist E, F ⊂ ℤ_{n} such that they are not translates of each other, however they have the same 3-deck.

Proof. Let

A = \{\frac{l_{1}n}{q} + kd : k ∈ \{0, 1, …, r − 1\}, l_{1} ∈ \{0, 1, …, q − 1\}\} ,

B = \{\frac{l_{2}n}{p} + kd : k ∈ \{0, 1, …, r − 1\}, l_{2} ∈ \{0, 1, …, p − 1\}\} ,

E = A ∪ (B + 1)  and  F = A ∪ (B + d + 1).

Then

χ̂_{E}(s) = \underbrace{(∑_{k=0}^{r−1} e^{−2πi \frac{kds}{n}} )}_{0 if pq|s but pqr∤s}· ( \underbrace{∑_{l_{1}=0}^{q−1} e^{−2πi \frac{l_{1}s}{q}}}_{q if q|s, 0 if q∤s}+e^{−2πi \frac{s}{n}} · \underbrace{∑_{l_{2}=0}^{p−1} e^{−2πi \frac{l_{2}s}{p}}}_{p if p|s, 0 if p∤s})

and

χ̂_{F} (s) = (∑_{k=0}^{r−1} e^{−2πi \frac{kds}{n}} ) · (∑_{l_{1}=0}^{q−1} e^{−2πi \frac{l_{1}s}{q}} + e^{−2πi \frac{s(d+1)}{n}} · ∑_{l_{2}=0}^{p−1} e^{−2πi \frac{l_{2}s}{p}} ) .

Thus

χ̂_{E}(s) ≠ 0 ⟺ χ̂_{F} (s) ≠ 0 ⟺ (p|s or q|s) and (pq |̸s or pqr|s),

hence

supp χ̂_{E} = \underbrace{\{s ∈ ℤ_{n} : p|s, q |̸s\}}_{S_{p}} ∪ \underbrace{\{s ∈ ℤ_{n} : q|s, p |̸s\}}_{S_{q}} ∪ \underbrace{\{s ∈ ℤ_{n} : pqr|s\}}_{S_{pqr}} .

For checking that E and F have the same 3-deck we have to show that

s_{1} + s_{2} + s_{3} = 0(mod n) ⟹ χ̂_{E}(s_{1})χ̂_{E}(s_{2})χ̂_{E}(s_{3}) = χ̂_{F} (s_{1})χ̂_{F} (s_{2})χ̂_{F} (s_{3}).  (17)

We have nothing to prove unless s_{1}, s_{2}, s_{3} ∈ supp χ̂_{E}. So suppose that s_{1}, s_{2}, s_{3} ∈ supp χ̂_{E}. Note that χ̂_{E}(s) = χ̂_{F} (s) unless s ∈ S_{p}. Thus if none of s_{1}, s_{2}, s_{3} are in S_{p} then we are done. It is impossible that exactly one of them is in S_{p} (because of divisibility by q).

If two of them, say s_{1} and s_{2}, are in S_{p} then s_{3} is in S_{p} or in S_{pqr}. In both cases it is easy to check (17).

Finally, suppose that F = E + t (mod n). Since both E and F have qr elements that are 0 mod d and pr elements that are 1 mod d, t must be of the form t = md. Thus we must have A = A+md and B + d = B + md (mod n). But B consists of blocks which are arithmetic progressions of length r and step d, and these are regularly spaced at intervals of length qrd. Hence B +d = B +md (mod n) can only happen if d − md is a multiple of qrd, or, equivalently, if m = 1 mod qr. On the other hand, by the similar structure of A it follows that m = 0 mod pr, which is a contradiction.

2.3 Results about real-valued functions

Given the results we have proved so far we can also characterize those values of n for which the 3-deck determines the characteristic function of any nonempty subset of ℤ_{n} up to translation even among all ℤ_{n} → ℝ functions.

Theorem 2.24. For n ≥ 3 the following three statements are equivalent.

(i) n is a power of an odd prime or n is the product of at most 3 (not necessarily distinct) odd primes.

(ii) The support of the Fourier Transform of any characteristic function on ℤ_{n} is an extendable domain.

(iii) If for some ∅ ≠ E ⊂ ℤ_{n} and g : ℤ_{n} → ℝ, χ_{E} and g have the same 3-deck then they are translates of each other.

Proof. (i)⇒(ii): This is exactly Proposition 2.4.

(ii)⇒(iii): If E ≠ ∅ then χ̂_{E}(0) ≠ 0 and so by Lemma 2.3 (2) we get that χ_{E} and g are indeed translates of each other.

(iii)⇒(i): If n is odd and (i) does not hold then, by Theorem 2.23, there exists counterexamples for (iii), even with g being a characteristic function.

Now suppose that n > 2 is even and let E = {1, 2, …, n/2}. It is easy to check that supp χ̂_{E} = {0, 1, 3, 5, …, n − 1}. Let

h_{α}(l) = \begin{cases}α & if l = 1, \\ −α & if l = −1, \\ 0 & otherwise. \end{cases}

Let g_{α} be the inverse Fourier Transform of the function G_{α}(l) = e^{2πih_{α}(l)} · χ̂_{E}(l) on ℤ_{n}. Since h_{α} is an odd function, G_{α}(−l) = \overline{G_{α}(l)}, and so g_{α} is a real valued function. Since h_{α} is additive on supp χ̂_{E}, the right hand side of (3) holds for k = 3, f and g = g_{α}, and so N_{χ_{E},3} = N_{g_{α},3}. This way we get continuum many distinct g_{α} : ℤ_{n} → ℝ functions. Since χ_{E} has only finitely many translates (iii) cannot hold for every g_{α}.

Example 2.25. Let n ≥ 4 be arbitrary, f = 0 on ℤ_{n} and g(k) = cos \frac{2kπ}{n} (k ∈ ℤ_{n}). Then clearly f̂ = 0 and one can check that

ĝ(l) = \begin{cases}n/2 & if l = 1, \\ −n/2 & if l = −1, \\ 0 & otherwise. \end{cases}

Then it is easy to check that the righthand-side of (3) holds for k = 3, so N_{f,3} = N_{g,3}, however f and g are clearly not translates of each other.

This shows that if we allow E = ∅ in (iii) of Theorem 2.24 then (i)⇒(iii) is not true any more.

Remark 2.26. It is proved in [JK] (Proposition 2.7) that if f is the characteristic function of a subset of ℝ of finite measure and g ∈ L^{1}(ℝ) is a nonnegative function such that N_{f,3} = N_{g,3} then there g must be equal to a characteristic function almost everywhere.

One can check that the same proof works on ℤ_{n} as well. This has the following consequences.

1. The characteristic functions on ℤ_{n} are determined up to translation by their 3-deck among nonnegative functions if and only if they are determined up to translation among characteristic functions; that is, by Corollary 1.1, if and only if n is a power of an odd prime or n is the product of at most three (not necessarily distinct) odd primes or n ∈ {2, 4, 6, 8, 10}.

2. Only the (at most finitely many) characteristic functions can be nonnegative among the (continuum many) g_{α} functions of the proof of (iii)⇒(i) of Theorem 2.24.

3 The percentage of subsets of ℤ_{n} not determined by their 3-deck up to translation

As we mentioned in the Introduction, in [RS1] Radcliffe and Scott proved that almost all subsets of ℤ_{n} are determined up to translation by their 3-deck. More specifically they proved that the fraction of subsets of ℤ_{n} whose Fourier Transform vanishes somewhere is at most C_{ϵ}/n^{1/2−ϵ}, for any ϵ > 0, and, since any set whose FT does not vanish is uniquely determined from its 3-deck, this proves that a fraction at most C_{ϵ}/n^{1/2−ϵ} of the possible sets are not determined by their 3-deck.

Furthermore, it is easy to see that the probability of having the FT of a random subset of ℤ_{n} vanish somewhere is at least C/\sqrt{n}. For this one takes n to be even and examines the FT of the random set at n/2. The vanishing there is equivalent to a random subset of a set of n/2 ones and n/2 minus-ones having a vanishing sum. This probability is equal to \binom{n}{n/2}/2^{n} ∼ C/\sqrt{n}.

However, here we show that the probability that a random subset of ℤ_{n} is not uniquely determined up to translation by its 3-deck is exponentially small (Theorem 3.4). When talking about random sets in this section we mean that all subsets of ℤ_{n} are equally probable. This is the same as tossing an independent fair coin for each element of ℤ_{n} to decide membership in the random set.

Lemma 3.1. Suppose u_{1}, …, u_{m} are vectors in a vector space V and that the collection u_{1}, …, u_{D}, D ≤ m, are linearly independent. Suppose also that ϵ_{j}, j = 1, …, m, are {0, 1}-valued random variables which are unbiased and independent. Then

ℙr [∑_{j=1}^{m} ϵ_{j}u_{j} = 0] ≤ 2^{−D}.  (18)

Proof. Since u_{1}, …, u_{D} are independent, for any fixed ϵ_{D+1}, …, ϵ_{m}, the 2^{D} possible values of ∑_{j=1}^{m} ϵ_{j}u_{j} are all distinct, so only at most one of them can be zero.

Corollary 3.2. If E ⊆ ℤ_{n} is random then

ℙr [χ̂_{E}(k) = 0] ≤ 2^{−Cn/(k,n) log log n},

for some absolute constant C > 0 and for all k ∈ ℤ_{n}.

Proof. Let ω = e^{2πi/n}. Then

χ̂_{E}(k) = ∑_{j=0}^{n−1} ϵ_{j}ω^{kj},  (19)

where the ϵ_{j}, j = 0, …, n − 1, are independent, unbiased, {0, 1}-valued random variables.

It is well known that the algebraic order of ω^{k} over the field ℚ is ϕ(n/(k, n)), where ϕ(n) is the Euler function which counts how many numbers from 1 to n are coprime to n. It is also well known [HW] that ϕ(n) ≥ Cn/log log n. This means that if P (x) is a polynomial with rational coefficients and degree < Cn/(k, n) log log n then P (ω^{k}) ≠ 0. This, in turn, implies that the complex numbers

1, ω^{k}, ω^{2k}, …, ω^{(Cn/(k,n) log log n)·k}

are ℚ-linearly independent. Applying Lemma 3.1 to the random sum (19) in the vector space ℂ over ℚ we get our result.

Corollary 3.3. If n is odd then the probability that a random subset of ℤ_{n} is not uniquely determined by its 3-deck is at most 2^{−Cn/ log log n}.

Proof. We make use of a result of Grünbaum and Moore [GM] (see §1.1) which states that if n is odd, E ⊆ ℤ_{n}, and χ̂_{E}(1) ≠ 0 then E is determined by its 3-deck. The rest follow from Corollary 3.2 with k = 1.

For arbitrary n we lose a little in the exponent. Probably this is unnecessary.

Theorem 3.4. If E is a random subset of ℤ_{n} the probability that E is not determined by its 3-deck is at most

2^{−C_{ϵ}n^{1−ϵ}},

for any ϵ > 0.

For the proof we use some notions (recall Definition 2.2 and Notation 2.5) and lemmas from §2.1 and also some new ones. Write

A_{x} = {k ∈ ℤ_{n} : (k, n) ≤ x},

and write GAP(B) for the size of the largest interval contained in the complement of B ⊆ ℤ_{n}.

Lemma 3.5. GAP(A_{d(n)}) ≤ d(n), where d(n) denotes the number of divisors of n.

Proof. Suppose that I = {a, a + 1, …, a + d(n)} ⊆ A_{d(n)}^{c} is an interval of size d(n)+1, and i, j ∈ I, i ≠ j. Then (i, n) > d(n) and (j, n) > d(n). It follows that (i, n) ≠ (j, n), otherwise we would have |i − j| ≥ (i, n) > d(n), which cannot happen as all distances in I are at most d(n). Thus, to each i ∈ I there corresponds a different divisor of n, namely (i, n). But this cannot happen as I has d(n) + 1 members but there are only d(n) different divisors of n. □

Lemma 3.6. If {0, 1, …, d} ⊂ A ⊂ ℤ_{n} and GAP(A) ≤ d then A is an extendable domain.

Proof. Let h : A → ℝ/ℤ be an additive function. We prove that h satisfies h(j) = jh(1) (mod 1), for all j ∈ A, which means, by definition, that A is indeed an extendable domain.

If 1 ≤ j ≤ d then h(j) = h(j − 1) + h(1) (mod 1), since 1, j − 1, j all belong to A, hence by induction we have our claim for j up to d. Suppose d < J ∈ A and that we have proved h(j) = jh(1) (mod 1) for all j ∈ A, j < J. Since GAP(A) ≤ d, it follows that there is a j′ ∈ A ∩ {J − d, …, J − 1}. By our inductive assumption we have h(j′) = j′h(1) (mod 1) and we also know h(J − j′) = (J − j′)h(1) (mod 1), as J − j′ ≤ d. The additivity of h on A implies h(J) = Jh(1) (mod 1).

Lemma 3.7. If E ⊂ ℤ_{n} and {1, 2, …, d(n)} ⊂ supp χ̂_{E} then E is determined up to translation by its 3-deck.

Proof. By Fact 2.6, {1, 2, …, d(n)} ⊂ supp χ̂_{E} implies that A_{d(n)} ⊂ supp χ̂_{E}. Thus by Lemma 3.5, GAP(supp χ̂_{E}) ≤ d(n). Hence by Lemma 3.6, supp χ̂_{E} is an extendable domain. Therefore by Lemma 2.3 (1), E is determined up to translation by its 3-deck.

Proof. (Theorem 3.4) By Corollary 3.2,

ℙr [∃j ∈ {1, 2, …, d(n)} : χ̂_{E}(j) = 0] ≤ d(n)2^{−Cn/d(n) log log n}
≤ C_{ϵ}n^{ϵ}2^{−C_{ϵ}n^{1−ϵ}}
≤ 2^{−C_{ϵ′}n^{1−ϵ′}} ,

where ϵ′ > 0 is again arbitrary, and we used the fact that d(n) = O(n^{ϵ}) for all ϵ > 0 [HW]. By Lemma 3.7, this completes the proof of Theorem 3.4.

References

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

[GM] F. A. Grünbaum and C. C. Moore The use of higher-order invariants in the determination of generalized Patterson cyclotomic sets, Acta Cryst. Sect. A 51 (1995), no. 3, 310–323.

[HW] G.H. Hardy and E.M. Wright, An introduction to the theory of numbers, Fifth Edition, Oxford Univ. Press, 1978.

[JK] P. Jaming and M.N. Kolountzakis, Reconstruction of functions from their triple correlations, New York J. Math. 9 (2003), 149-164.

[L] H.W. Lenstra, Generating units modulo an odd integer by addition and subtraction, Acta Arith. 64, 4, 383–388.

[LWW] A. Lohmann, G. Weigelt and B. Wirnitzer, Speckle masking in astronomy: triple correlation theory and application, Appl. Opt. 22 (1983), 4028–4037.

[P] L. Pebody, The reconstructibility of finite abelian groups, Comb. Probab. Computing 13 (2004), 867-892.

[P2] L. Pebody, Reconstructing odd necklaces, manuscript.

[PRS] L. Pebody, A.J. Radcliffe and A.D. Scott, Finite subsets of the plane are 18reconstructible, SIAM J. Discr. Math. 16 (2003), 2, 262-275.

[Pet] A. Petropulu, Higher-order spectral analysis, in Digital Signal Processing Handbook, V.K. Madisetti and D.B. Williams, editors, Chapman & Hall/CRCnetBASE, 1999.

[RS1] A. J. Radcliffe and A. D. Scott Reconstructing subsets of ℤ_{n}, J. Combin. Theory Ser. A 83 (1998), no. 2, 169–187.

[RS2] A. J. Radcliffe and A. D. Scott Reconstructing subsets of reals, Electron. J. Combin. 6 (1999), no. 1, Research Paper 20, 7 pp. (electronic)