Timeline for Generator size for cyclic groups
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 13, 2013 at 15:33 | comment | added | Igor Rivin | The results mentioned in the Wikipedia article suggest that the question on $O(\log p)$ bounds has been asked a long time ago, and the negative results are to show that you certainly can't do better (after all, why not $O(\sqrt(\log p))$? A priori, no reason). Notice that the best (conditional) estimates on quadratic non-residues are $O(\log^2 p),$ so this is a lower bound on how well you can do with current technology. | |
| Jul 13, 2013 at 15:30 | comment | added | Turbo | But he seems to have a conjectureon page 1725 relating to $\exp(\gamma)$? Plus in the last few lines he seems to suggest $O(\log{p}\log\log{p})$ may be possible? Is this unrelated? | |
| Jul 13, 2013 at 15:25 | comment | added | Igor Rivin | Note that Bach does NOT look at the smallest residue, so this is not an improvement as far as your question is concerned. | |
| Jul 13, 2013 at 15:15 | comment | added | Turbo | Hi Igor: It seems there are improvements. ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/… | |
| Jul 13, 2013 at 14:04 | comment | added | Igor Rivin | I don't understand: The wikipedia article you cite seems to give the state of the art on this question (and seems to indicate that there is a good chance that the answer to the question is "no". | |
| Jul 13, 2013 at 10:11 | history | edited | Turbo | CC BY-SA 3.0 |
added 136 characters in body
|
| Jul 13, 2013 at 10:06 | history | asked | Turbo | CC BY-SA 3.0 |