Skip to main content
added 661 characters in body
Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

While $M=n^{O_p(1)}$ can be tricky (or out of reach), improving the trivial bound $M\le p^{\varphi((p-1)n)}$ one can showfollowing argument shows that, indeed $M\le p^{(2+o(1))\sqrt{dn}}$ with $d=\gcd(p-1,n)$; thus, $M\le p^{(2+o(1))\sqrt{(p-1)n}}$ holds$M<\exp(O(\sqrt n))$ in the regime where $p$ is fixed and $n$ grows. To this end, recall

Recall that the critical number of a finite abelian group $G$ is defined to be the smallest positive integer $k$$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 elements of pairwise distinct elements of $A$. It is known that theif $G$ is cyclic, then its critical number of any finite abelian group is at most $(2+o(1))\sqrt{|G|}$ (just google; see, for instance the references)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}/((p-1)n){\mathbb Z}$${\mathbb Z}/dn{\mathbb Z}$, so that $k\le(2+o(1))\sqrt{(p-1)n}$$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{(p-1)n}$$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}\}\subset {\mathbb Z}/((p-1)n){\mathbb Z}$$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 equal todivisible by $0$$dn$, and we define $M$ to be the claim followssum 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.

While $M=n^{O_p(1)}$ can be tricky (or out of reach), improving the trivial bound $M\le p^{\varphi((p-1)n)}$ one can show that, indeed, $M\le p^{(2+o(1))\sqrt{(p-1)n}}$ holds. To this end, recall that the critical number of a finite abelian group $G$ is defined to be the smallest positive integer $k$ such that for any $k$-element subset $A\subset G\setminus\{0\}$, every element of $G$ is representable as a non-empty sum of elements of pairwise distinct elements of $A$. It is known that the critical number of any finite abelian group is at most $(2+o(1))\sqrt{|G|}$ (just google for the references).

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

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.

Source Link
Seva
  • 23k
  • 2
  • 59
  • 141

While $M=n^{O_p(1)}$ can be tricky (or out of reach), improving the trivial bound $M\le p^{\varphi((p-1)n)}$ one can show that, indeed, $M\le p^{(2+o(1))\sqrt{(p-1)n}}$ holds. To this end, recall that the critical number of a finite abelian group $G$ is defined to be the smallest positive integer $k$ such that for any $k$-element subset $A\subset G\setminus\{0\}$, every element of $G$ is representable as a non-empty sum of elements of pairwise distinct elements of $A$. It is known that the critical number of any finite abelian group is at most $(2+o(1))\sqrt{|G|}$ (just google for the references).

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