Difference bases in simple cyclic groups

Question

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

Answer 1

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.

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