Timeline for Sets with both additive and multiplicative gaps
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 24, 2022 at 14:31 | comment | added | Ivan Meir | @Seva Awesome - very much appreciated thank you. | |
| Jul 24, 2022 at 14:19 | comment | added | Seva | @IvanMeir: There are about $p/4$ quadratic residues immediately followed by a quadratic nonresidue; and then, there are about $p/4^2$ residues followed by two more residues and a nonresidue, etc.; now, $1/4+1/4^2+1/4^3+...=1/3$. | |
| Jul 24, 2022 at 13:27 | comment | added | Ivan Meir | To clarify - I understand why the set satisfies the conditions of the problem but not the density calculation. | |
| Jul 24, 2022 at 13:26 | comment | added | Ivan Meir | Apologies but I can't see how your example with $p\equiv\pm3\pmod 8$ example gives a density of $1/3 + o(1)$. Could you give a brief explanation please? Thanks | |
| Jul 22, 2022 at 16:22 | vote | accept | Seva | ||
| Jul 22, 2022 at 10:33 | comment | added | Ivan Meir | A `trivial observation is that since your graph has $2p$ edges and hence $p^2/2(1-4/p)$ non-edges Turan's Theorem gives an independent set of size $p/4$ and hence a density of 1/4 for any $p$. | |
| Jul 21, 2022 at 19:44 | history | became hot network question | |||
| Jul 21, 2022 at 12:53 | answer | added | Will Sawin | timeline score: 23 | |
| Jul 21, 2022 at 12:46 | comment | added | Thomas Bloom | A very nice question! I think even a simple greedy construction achieves density $1/3$. The fact that the same density threshold is reached by a trivial greedy argument, an additively structured construction (your first) and a multiplicatively structured construction (your second) is surprising. | |
| Jul 21, 2022 at 11:42 | history | asked | Seva | CC BY-SA 4.0 |