1
$\begingroup$

Suppose

$$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$

We calculate the differences as:

$$ d=p_i-p_j\mod N,\quad i\ne j $$

Now let $a_d$ denote the number of occurrence of $d$ (for $d = 0, 1, 2, \dots , N − 1$), then we have a set

$$ D=\{a_0,a_1,a_2,...,a_{N-1} \} $$

Let's define a valid $D$ as a $D$ which is resulted from a points set $P$ (a $D$ which there exists some $P$ leading to it).

Reconstructing $P$ from $D$ is called beltway reconstruction and there are some algorithms for it, but I'm looking for some criteria that indicate the given $D$ is not a valid one.

One is $\sum_{d=1}^{N-1} a_d = K(K-1)$, i.e. if this equality doesn't hold for the given $D$ that $D$ is not a valid one.

The other is $a_i = a_{N-i}$ for $i=1,2,\cdots,N-1$

EDIT: consider these two sets of $D$'s ($a_0=K$ is included, too)

$(N,K) = (10,5)$:

$$\color{green}{\{5, 3, 2, 2, 2, 2, 2, 2, 2, 3\}}$$

$$\{5,2, 3, 2, 2, 2, 2, 2, 3, 2\}$$

$$\color{green}{\{5, 2, 2, 3, 2, 2, 2, 3, 2, 2\}}$$

$$\{5,2, 2, 2, 3, 2, 3, 2, 2, 2\}$$

$(N,K) = (11,8)$ :

$$\color{green}{ \{ 8, 6 , 6, 6 , 5, 5 , 5, 5 , 6, 6 , 6 \}}$$

$$\{ 8 , 6 , 6 , 5 , 6 , 5 , 5 , 6 , 5 , 6 , 6\}$$

$$\{ 8 , 6 , 6 , 5 , 5 , 6 , 6 , 5 , 5 , 6 , 6\}$$

$$\color{green}{\{ 8 , 6, 5 , 6, 6 , 5, 5 , 6, 6 , 5, 6 \}}$$

$$\{ 8, 6 ,5, 6 ,5, 6 ,6, 5 ,6, 5 ,6\}$$

$$\color{green}{\{ 8 , 6 , 5 , 5 , 6 , 6 , 6 , 6 , 5 , 5 , 6 \}}$$

$$\{ 8 , 5 , 6 , 6 , 6 , 5 , 5 , 6 , 6 , 6 , 5\}$$

$$\color{green}{\{ 8 , 5 , 6 , 6 , 5 , 6 , 6 , 5 , 6 , 6 , 5 \}}$$

$$\color{green}{\{ 8 , 5 , 6 , 5 , 6 , 6 , 6 , 6 , 5 , 6 , 5 \}}$$

$$\{ 8 ,5, 5 ,6, 6 ,6, 6 ,6, 6 ,5, 5\}$$

Only green ones are permissible and the others are not, while they satisfy symmetric criteria suggested thanks to Thomas. So there must be some asymmetric criteria.

Are there any other criteria?

This question is related, if helps.

$\endgroup$
2
  • $\begingroup$ There certainly must be other criteria, e.g., for $N=5$, $K=4$, there are many $D$ satisfying the two criteria given, but only one is valid. $\endgroup$ Commented Aug 4, 2013 at 23:56
  • $\begingroup$ @GerryMyerson Thanks for sharing your knowledge sincerely. Yes You are right, actually these are necessary conditions, and I'm looking for more necessary conditions. $\endgroup$ Commented Aug 5, 2013 at 6:41

1 Answer 1

3
+50
$\begingroup$

There are no doubt quite a few more necessary conditions; below are a couple of observations. I'm not sure how useful these are, without knowing your motivation.

(I will consider with $a_0$ also included, since this is always $K$, so we may assume that this condition is satisfied and convert the following conditions accordingly.)

$L_p$ bounds - as you point out, there is a forced $L_1$ bound:

$$ \sum_{n=0}^{N-1}a_n= K^2.$$

There is an obvious $L_\infty$ bound: $0\leq a_n\leq K$ for all $n$. Using the usual inequalities one may get similar bounds for all $L_p$ norms; for example,

$$ K^2\leq \sum_{n=0}^{N-1}a_n^2\leq K^3. $$

Perhaps more useful is the observation that $a_n$ must be a positive definite measure, that is, its Fourier coefficients are all real and positive, so:

$$ 0 \leq \sum_{n=0}^{N-1}a_n e( mn/N ) \leq K^2 $$

for all $0\leq m < N$.

A good place to look is in the recent paper by Schoen and Shkredov, 'Higher moments of convolutions', which provides a host of useful results about $A\ast (-A)(n)$ (equivalent to your $a_n$).

Edit: more details. $a_n\geq 0$ because it counts the number of representations of $n$ as $p_1-p_2$ any count is non-negative. $a_n\leq K$ because otherwise by the pigeonhole principle there would be three distinct $p_1,p_2,p_3\in P$ such that $p_1-p_2=n=p_1-p_3$, a contradiction.

Expanding out $\sum a_n^2$ using the definition shows that it is the count of all quadruples $p_1,p_2,p_3,p_4\in P$ such that $p_1-p_2=p_3-p_4$ (this is often known as the additive energy of $P$). This is at least $K^2$ from the trivial quadruples with $p_1=p_3$ and $p_2=p_4$. It is at most $K^3$ because fixing any three of the quadruple uniquely determines the fourth.

Edit: an asymmetric criterion to handle the cases in the question. That is, in $\mathbb{Z}/10\mathbb{Z}$ why is (again, including $n=0$ case here) $$ (5,3,2,2,2,2,2,2,2,3) $$ permissible but $$ (5,2,3,2,2,2,2,2,3,2) $$ is not? We pass to the subgroup $\mathbb{Z}/5\mathbb{Z}$. Since this has index 2 in $\mathbb{Z}/10\mathbb{Z}$ we must be able to partition $P$ into two sets (the intersection with the two cosets) such that the difference from any two elements of the same set is in $\mathbb{Z}/5\mathbb{Z}$, and the difference from any elements belonging to opposing sets is not. Hence looking at the $\mathbb{Z}/5\mathbb{Z}$ piece for each set: $$ (5,2,2,2,2) $$ and $$ (5,3,2,2,3) $$ respectively, each must be the sum of two vectors which is 'permissible', now within $\mathbb{Z}/5\mathbb{Z}$.

But this is ruled out by the $L_1$ necessary condition: the sum of all the components in the first is 13 = 4 + 9, so that's fine. But the sum of the all the components in the second is 15, which is not the sum of two squares. But the decomposition into two sets would give such a sum, a contradiction.

The same argument generalised gives the following criterion (a 'permissible' vector is a vector which arises from a difference set in that group):

If a vector $v$ is permissible then for every subgroup $H\leq \mathbb{Z}/N\mathbb{Z}$, if $v'$ denotes the restriction of $v$ to $H$, then $v'$ is the sum (as a vector) of $N/\lvert H\rvert$ many permissible (within $H$) vectors (not necessarily distinct). In particular, the sum of the components within $v'$ is the sum of $N/\lvert H\rvert$ squares.

Of course, this last point is not very useful when $N/\lvert H\rvert\geq 4$. But the other necessary conditions must also hold, so one of those could be used instead.

This is starting to feel like a necessary and sufficient condition, in a local to global kind of philosophy. Are there any examples when $N$ is prime that the 'symmetric' criteria don't rule out?

$\endgroup$
6
  • $\begingroup$ @Thomson Thanks for your contribution. How do you concluded that $0\leq a_n\leq K$, and $K\leq \sum_{n=0}^{N-1}a_n^2\leq K^3$ ? $\endgroup$ Commented Aug 5, 2013 at 14:25
  • $\begingroup$ I've explained in the edit (also corrected a typo - the lower bound for the $L_2$ bound should be $K^2$ not $K$). $\endgroup$ Commented Aug 5, 2013 at 14:52
  • $\begingroup$ Your contribution was great. Is there any criteria which are not symmetric over all $a_n$'s e.g. $\sum a_n$ or $\sum a_n^2$ , ... . Would you mind reading the EDIT part of the question? Thanks $\endgroup$ Commented Aug 6, 2013 at 6:57
  • $\begingroup$ Done; see edit. $\endgroup$ Commented Aug 6, 2013 at 8:18
  • $\begingroup$ Which part don't you understand? You need to look up what a 'coset' of a subgroup is. The index is just the number of cosets, or (by Lagrange's theorem) the size of the group divided by the size of the subgroup. $\endgroup$ Commented Aug 6, 2013 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .