3
$\begingroup$

I've encountered the following question in my research:

Let $A$ be a subset of $\mathbb{Z}/n\mathbb{Z}$. Let me call $A$ "sum-free" if there is no solution to $x+y=z$ for $x,y,z \in A$ with distinct $x$ and $y$. The addition is of course mod $n$.

Question: For which $n$ is the set $A = \{2^x \!\!\mod n: x>0\}$ (the set of powers of $2$) sum-free? I'm assuming that $n$ is odd.

Does anyone have an idea how to approach this question?

$\endgroup$
6
  • $\begingroup$ For most $n$ it's probably not, or at least for most prime $n$, because on average powers of $2$ are at least conjecturally a positive proportion of numbers mod $p$. $\endgroup$
    – Will Sawin
    Jul 1, 2015 at 13:49
  • 1
    $\begingroup$ What are the values of $n$ smaller than, say, $100$, with the property in question? What does OEIS say? $\endgroup$
    – Seva
    Jul 1, 2015 at 16:20
  • 1
    $\begingroup$ @Seva If my program is correct, the first few odd $n$ with the property are 1, 3, 7, 15, 21, 31, 51, 63, 73, 85, 89, 91, 93, 105, 117, 127, 133, 151, 195. This sequence is not in the OEIS. $\endgroup$ Jul 1, 2015 at 20:03
  • $\begingroup$ I find $379$ such numbers $\leq 10000$. $\endgroup$
    – Stefan Kohl
    Jul 1, 2015 at 20:49
  • $\begingroup$ A numerical test up to $2 \cdot 10^6$ seems to say that the order of 2 for such n is around $\sqrt{n}$, so Jeremy's heuristic is right. $\endgroup$
    – user75584
    Jul 1, 2015 at 22:20

1 Answer 1

3
$\begingroup$

This question is very similar to the one here, and the heuristic should apply equally well. In particular, $A$ is sum-free if and only if there does not exist a $k$ with $k \ne \frac{n+1}{2}$ so that $k$ and $1-k$ are both in $A$, and the chances of this occurring are approximately $e^{-r^{2}/\phi(n)}$, where $r = |A|$. Hence, one should only expect $A$ to be sum-free if $|A| \approx \sqrt{\phi(n)}$. This is a very infrequent situation, but it is certainly not impossible. (In particular, it is easy to see that if $n = 2^{k} - 1$, then $A$ is sum-free. Also, one could look for divisors $n$ of $2^{k} - 1$ with $n \gg k^{2}$ to find other examples where $A$ is sum-free.)

$\endgroup$

Your Answer

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

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