Any natural number $n$ coprime with a prime number $p$ is a divisor of $M=1+p+p^2+\dots+P^{N-1}$ where $N\leq \varphi((p-1)n)$ is the order of $p$ in $\left(\mathbb Z/((p-1)n)\mathbb Z\right)^*$.

The integer $M$ is minimal with this property and is of course in general exponentially larger than $n$.

(Added correction: The minimal integer M is in fact given by $N=\varphi(n)$ for $n$ coprime to $p-1$. Thanks to Seva for this remark.)

Can this exponential bound be improved to a polynomial one when allowing digits in $\{0,1\}$? Otherwise stated, given a prime number $p$, does there exist a constant $\alpha=\alpha(p)$ such that every natural integer $n$ has a non-zero multiple $M=dn$ with $M\leq n^\alpha$ a sum of distinct powers of $p$?

(The result is of course trivially true for $p=2$.)

There are of course many related questions:

If yes, what is asymptotically the best constant $\alpha$ (i.e. we want $M\leq n^{\alpha(1+\epsilon)}$ for all $\epsilon>0$ and for all but a finite number of $n$)?

How does $\alpha$ grow with $p$? (A trivial lower bound comes from a counting argument.)


Added after a comment of Douglas Zare: The question makes of course perfectly sense for non-prime $p\geq 2$.

  • $\begingroup$ Coincidentally, I just answered a different but related question here: programmers.stackexchange.com/questions/272517/… $\endgroup$ Apr 23 '15 at 12:17
  • $\begingroup$ The question makeds however no much sense for non-prime $p$, except by removing an obvious set of "bad" integers from $\mathbb N$. $\endgroup$ Apr 23 '15 at 13:10
  • $\begingroup$ Which part doesn't make sense for non-prime $p$? $\endgroup$ Apr 23 '15 at 13:16
  • $\begingroup$ Sorry, I was mistaken. There are no problems for $p$ non-prime with my question. $\endgroup$ Apr 23 '15 at 13:42
  • 5
    $\begingroup$ The question would have a simple answer if you were allowing $-1$ as a coefficient. In this case, for $k\ge\log_2n$, at least two of the sums $\epsilon_0+\epsilon_1p+\dotsb+\epsilon_kp^k$ are congruent modulo $n$, and their difference is an algebraic sum of powers of $p$, divisible by $n$. Thus, you can take $\alpha=\log_2 p$ in this case. $\endgroup$
    – Seva
    Apr 23 '15 at 15:14

While $M=n^{O_p(1)}$ can be tricky (or out of reach), the following argument shows that $M\le p^{(2+o(1))\sqrt{dn}}$ with $d=\gcd(p-1,n)$; thus, $M<\exp(O(\sqrt n))$ in the regime where $p$ is fixed and $n$ grows.

Recall that the critical number of a finite abelian group $G$ is defined to be the smallest positive integer $k=k(G)$ such that for any $k$-element subset $A\subset G\setminus\{0\}$, every element of $G$ is representable as a non-empty sum of pairwise distinct elements of $A$. It is known that if $G$ is cyclic, then its critical number is at most $(2+o(1))\sqrt{|G|}$; see, for instance the paper by Hamidoune, Llado, and Serra "On Complete Subsets of the Cyclic Group".

Let now $k$ being the critical number of the group ${\mathbb Z}/dn{\mathbb Z}$, so that $k\le(2+o(1))\sqrt{dn}$. If the order of $p$ in this group does not exceed $k-1$, then we have $p^s\equiv 1\pmod{dn}$ with some $s\le k-1$, implying $n\mid 1+p+\dotsb+p^{s-1}$; thus, we can set $M:=1+p+\dotsb+p^{s-1}$. Otherwise, consider the set $A:=\{1,p,p^2,\ldots,p^{k-1}\}$. By the definition of a critical number, one can select several elements from this set so that their sum is divisible by $dn$, and we define $M$ to be the sum of these numbers.

One further observation is that if $p\equiv 1\pmod n$, then in order for a sum of powers of $p$ to be divisible by $n$, one needs to have at least $n$ such powers; hence, $M>p^{n-1}$ in this case. This does not, of course, show that $M<n^{O(1)}$ fails to hold, as the assumption $p\equiv 1\pmod n$ is incompatible with the regime where $p$ is fixed and $n$ grows.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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