Sets with both additive and multiplicative gaps

Question

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$).

Answer 1

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$.