4
$\begingroup$

A subset $B$ of an abelian group $G$ is called a difference-basis if $B-B=G$. For a finite group $G$ by $\Delta(G)$ we denote the smallest cardinality of a difference basis of $G$. Let $C_n=\{z\in\mathbb C:z^n=1\}$ be the cyclic group of order $n$. Earlier works of Redei and Renyi (1949) imply that $\sqrt{n}\le\Delta(C_n)\le\sqrt{\frac43+o(1)}\sqrt{n}$. I am trying to attack the following

Problem N: Is $\lim_{n\to \infty}\frac{\Delta(C_n)}{\sqrt{n}}=1$?

Or at least its "prime" version:

Problem P: Is $\lim_{p\to \infty}\frac{\Delta(C_p)}{\sqrt{p}}=1$, where the limit is taken over all prime numbers $p$?

The affirmative answer to Problem P would follow from the affirmative answer to the following Problem B. Given a prime number $p$ and a generator $g$ of the (cyclic) multiplicative group $\mathbb Z_p^*$ of the field $\mathbb Z_p=\mathbb Z/p\mathbb Z$, let $\beta(p)$ be the smallest number $k$ such that the set $B_k=\{g^i:1\le i\le k\}$ is a difference-basis for $\mathbb Z_p$.

Problem B: Is $\lim_{p\to\infty}\frac{\beta(p)}{\sqrt{p}}=1$?

I calculated $\Delta(C_p)$ and $\beta(p)$ for all prime numbers $p\le 19$:

$\beta(2)=\Delta(C_2)=2$;

$\beta(3)=\Delta(C_3)=2$;

$\beta(5)=\Delta(C_5)=3$;

$\beta(7)=\Delta(C_7)+1=4$;

$\beta(11)=\Delta(C_{11})=4$;

$\beta(13)=\Delta(C_{13})+1=5$;

$\beta(17)=\Delta(C_{17})=5$;

$\beta(19)=\Delta(19)+1=6$.

Those "experimental" data suggest another problem.

Problem D: Is $\beta(p)-\Delta(C_p)\le 1$ for all prime numbers $p$?

If someone could write a program and calculate $\beta(p)$ and $\frac{\beta(p)}{\sqrt{p}}$ for larger prime $p$ I would be eager to see the results of calculations (I means how close is $\frac{\beta(p)}{\sqrt{p}}$ to 1).

$\endgroup$
2
$\begingroup$

I got to the 225th prime with quick-and-dirty Mathematica code

beta[n_]:=With[{p=Prime[n]},
 With[{l=PrimitiveRootList[p]},
  Module[{i,xl={},g},
   For[i=1,i<=Length[l],i++,
    g=l[[i]];
    Module[{s={0},x={g}},
     While[s!=Range[0,p-1],
      AppendTo[x,Mod[g Last[x],p]];
      s=Union[s,Mod[Most[x]-Last[x],p],Mod[Last[x]-Most[x],p]]
     ];
     AppendTo[xl,Length[x]]
    ]
   ];
   Min[xl]
  ]
 ]
]

(Outcome is different for different generators, I took the smallest one)

The result, I think, is sufficient to cast serious doubt on B. Here is the graph of $\frac{\beta(p)}{\sqrt{p}}$ for first 225 primes.

enter image description here

As for D, if my calculations are correct, $\beta(37)=9$ and $\Delta(C_{37})=7$

$\endgroup$
  • $\begingroup$ დიდი მადლობა Your calculations suggest that $\beta(p) will not solve Problems P or N, unfortunately. So, something different should be invented. $\endgroup$ – Taras Banakh Mar 8 '17 at 23:21

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.