15
$\begingroup$

I feel that the following problem should have a clean and simple solution, but so far I couldn't find one.

Suppose that $p$ is a prime, and that $A\subseteq\mathbb Z/p\mathbb Z$ is a set such that

  • for any $z\in\mathbb Z/p\mathbb Z$, either $z\notin A$ or $z+1\notin A$;
  • for any $z\in\mathbb Z/p\mathbb Z$, either $z\notin A$ or $2z\notin A$.

What is the largest possible density of such a set?

It is easy to construct a set $A$ with these properties of density $1/3+o(1)$, like for instance $\{2z\colon z\in(p/3,2p/3)\pmod p\}$. A more elaborated construction: assuming $p\equiv\pm3\pmod 8$, consider the set of all those quadratic residues $r$ such that if $r'$ is the smallest quadratic non-residue exceeding $r$, then $r'-r$ is odd. Can $A$ have a density exceeding $1/3+\varepsilon$ for infinitely many primes $p$, with fixed $\varepsilon>0$?

I also wonder what the expander properties and the eigenvalues of the corresponding graph are ($x,y\in\mathbb Z/p\mathbb Z$ connected by an edge whenever $y=x+1$, $y=x-1$, $y=2x$, or $y=x/2$).

$\endgroup$
6
  • 7
    $\begingroup$ A very nice question! I think even a simple greedy construction achieves density $1/3$. The fact that the same density threshold is reached by a trivial greedy argument, an additively structured construction (your first) and a multiplicatively structured construction (your second) is surprising. $\endgroup$ Jul 21, 2022 at 12:46
  • $\begingroup$ A `trivial observation is that since your graph has $2p$ edges and hence $p^2/2(1-4/p)$ non-edges Turan's Theorem gives an independent set of size $p/4$ and hence a density of 1/4 for any $p$. $\endgroup$
    – Ivan Meir
    Jul 22, 2022 at 10:33
  • $\begingroup$ Apologies but I can't see how your example with $p\equiv\pm3\pmod 8$ example gives a density of $1/3 + o(1)$. Could you give a brief explanation please? Thanks $\endgroup$
    – Ivan Meir
    Jul 24, 2022 at 13:26
  • $\begingroup$ To clarify - I understand why the set satisfies the conditions of the problem but not the density calculation. $\endgroup$
    – Ivan Meir
    Jul 24, 2022 at 13:27
  • 2
    $\begingroup$ @IvanMeir: There are about $p/4$ quadratic residues immediately followed by a quadratic nonresidue; and then, there are about $p/4^2$ residues followed by two more residues and a nonresidue, etc.; now, $1/4+1/4^2+1/4^3+...=1/3$. $\endgroup$
    – Seva
    Jul 24, 2022 at 14:19

1 Answer 1

23
$\begingroup$

I can give an upper bound of $2p/5$ and a lower bound of $(2/5-o(1))p$ for a conjecturally infinite set of $p$.

For the upper bound, the numbers $z, z+1, 2z+2, 2z+1, 2z$ form a pentagon in your graph so at most $2$ out of the $5$ may be in the set $A$. As $z$ runs over $\mathbb Z/p\mathbb Z$, each of $z, z+1, 2z+2, 2z+1, 2z$ run over $\mathbb Z/p\mathbb Z$, so adding up the number of members of $A$ in each of the $p$ pentagons we obtain $5 |A| \leq 2 p$, giving $|A| \leq 2p /5$.

For the lower bound, take $p=2^n-1$ to be a Mersenne prime. Then for $a \in \mathbb Z/p \mathbb Z$, the binary digits of $a/p$ after the "decimal" point are periodic with period $n$. The length of a string of zeroes in this decimal expansion is bounded, so there must be a longest length. Let $k_a$ be the place coming just before the first string of zeroes with the longest length, e.g. if the longest length is $3$ and $a/p = .10100010001\dots $ then $k_a=3$.

Let $c_a$ be the rational number obtained by taking $2^{k_a} a $, lifting from $\mathbb Z/p\mathbb Z$ to $\{0,\dots, p-1\}$, and then dividing by $2^{k_a}$. Note that $c_a$ is a rational number with denominator a power of $2$ and numerator a positive integer $<p$, and usually much smaller than $p$ since the string of digits is quite large.

Call $a$ good if $c_{a+1} =c_a+1$ and and $c_{2a} = 2 c_a$, and bad otherwise.

We can take $$A= \{ a \textrm{ good}, c_a \equiv 1 \textrm{ or } 4 \bmod 5 \}$$ and then we will have $|A|= (2/5- o(1))p$ as long as the number of bad $a$ is $o(p)$ (since that itself implies most good $a$ are in a large interval of good $a$).

We have either $a\notin A$ or $a+1\notin A$ because if $a\in A$ then $a$ is good and $c_a$ is congruent to $1$ or $4$ mod $5$ so $c_{a+1} = c_a + 1$ is congruent to $2$ or $0$ mod $5$, and thus $a+1\notin A$ (regardless of whether $a+1$ is good). For $2a$, it's the same argument, except congruent to $2$ or $3$ mod $5$.

So it suffices to, for each of the finitely many reasons that $a$ can be bad, show that the number of $a$ which are bad for that reason is $o(p)$.

This can be done as follows. Suppose $c_{a+1} \neq c_a$. The binary expansion of $c_{a+1}$ is obtained from $c_a$ by adding a $1$ in the $n-1$st place (and $2n-1$, and $3n-1, \dots$) and carrying. The only way that this can affect the first longest string of zeroes is if the longest string of zeroes contains the $n-1$st place, or the longest string of zeroes is followed by a string of $1$s that touches the $n-1$st place. These are both clearly events with probability going to $0$ as $n$ goes to $\infty$. If it doesn't do that, the only way it can change $k_a$ is if it creates a new, longer string of zeroes, which can only happen if $n-1$ ends a string of $1$s followed by the beginning of a string of zeroes whose total length is greater than the length of the largest existing string of zeroes. Since the length of the largest existing string of zeroes will typically be $\log n$, this is a low-probability event.

For multiplication by $2$, the argument is similar. The typical case is that this subtracts $1$ from $k_a$, leaving $c_a$ unchanged. Because it just shifts bits to the left, it fixes the length of the longest string of zeroes, so the only way it can do anything but subtract $1$ from $k_a$ is if it pushes the first bit of the first longest string of zeroes past the decimal point, i.e. if $k_a=1$. But this is again obviously a low probability event.


The adjacency matrix of the graph has a relatively large number of eigenvalues close to $4$. This is clearest to me if we look at the action of this adjacency matrix $M$ on a Fourier basis consisting of the vectors $v_\alpha$ whose $x$'th coordinate is $e(x\alpha/p)$ for $\alpha\in \mathbb Z/p\mathbb Z$. We have $M v_\alpha = v_{\alpha/2} + 2 \cos (2\pi /p) v_\alpha + v_{2\alpha}$. If we let $k$ be a small odd integer and $j$ a very small positive integer then $v_k + v_{2k} + v_{4k} + \dots + v_{2^jk}$ is close to an eigenvector with eigenvalue close to $4$, and these vectors are orthogonal. This can only happen if there are many eigenvectors with eigenvalues close to $4$.

$\endgroup$
8
  • 1
    $\begingroup$ $+1$, though the "local" argument you gave isn't that local. If you had something like $5z+1$ in your subgraph, then the argument wouldn't work if $n$ is a multiple of $5$, since it's then not the case that $5z+1$ runs over $\mathbb{Z}/n\mathbb{Z}$ as $z$ does. $\endgroup$ Jul 21, 2022 at 13:54
  • 2
    $\begingroup$ @mathworker21 But one can never connect $5z+1$ to $z$ only using the operations $z \mapsto z+1, z-1, 2z, z/2$ without using a congruence modulo a specific prime $p$. Local means any connected component of a finite subgraph one can form without using congruences mod $p$. $\endgroup$
    – Will Sawin
    Jul 21, 2022 at 14:01
  • $\begingroup$ @WillSawin Should $5 |A| \leq p$ be $5 |A| \leq 2p$ in your second paragraph? $\endgroup$
    – Ivan Meir
    Jul 21, 2022 at 14:51
  • $\begingroup$ That last paragraph should say $M v_\alpha = v_{\alpha/2} + 2 \cos (2\pi /p) v_\alpha + v_{2\alpha}$ not $M v_\alpha = v_{\alpha/2} + 2 \cos (2\pi \alpha/p) + v_{2\alpha}$, right? $\endgroup$ Jul 21, 2022 at 15:57
  • $\begingroup$ @WillSawin Very cool and interesting example for the lower bound! Can you give some indication how you came up with it? $\endgroup$
    – Ivan Meir
    Jul 24, 2022 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.