Timeline for How large must $A$ be if $\{1, \ldots, N\} \subseteq A-A$?
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 24, 2021 at 9:24 | answer | added | Jukka Kohonen | timeline score: 10 | |
| Jan 8, 2015 at 18:21 | comment | added | The Masked Avenger | In fact, the comment was also intended as a response to Seva, who remarked about an unsuccessful search. | |
| Jan 8, 2015 at 18:20 | comment | added | The Masked Avenger | @QinJianbin, yes, but the problems are related and a literature search on one should help with the other. | |
| Jan 8, 2015 at 16:51 | comment | added | Dan Petersen | Why the votes to close?? | |
| Jan 8, 2015 at 16:39 | comment | added | Seva | @Douglas Zare: It is important that $A$ needn't be contained in an interval of length $N$. | |
| Jan 8, 2015 at 16:02 | comment | added | Douglas Zare | Allowing negative numbers is unimportant because you can translate $A$. | |
| Jan 8, 2015 at 15:36 | comment | added | Qin Jianbin | @TheMaskedAvenger, There are two major difference between this problem and Golomb rulers. First, we allow negative numbers in A. Second, we allow duplicates (e.g. two pairs x, y \in A, can generate the same value). | |
| Jan 8, 2015 at 15:32 | comment | added | George Shakan | Suppose $N = k^2 - 1$. Consider $A = \{1 , \ldots , k\} \cup \{2k , 3k , \ldots , (k-1)k , k^2\}$. Then $A-A$ contains $\{1, \ldots , N\}$ and $|A| \sim 2 \sqrt{N}$. With sumset replacing difference set, see "a new upper bound for finite additive bases" by Gunturk and Nathanson. | |
| Jan 8, 2015 at 13:16 | comment | added | Yuichiro Fujiwara | @TheMaskedAvenger No perfect Golomb ruler of length larger than $6$ exists, though. So, essentially $\{0,1\}$, $\{0,1,3\}$, and $\{0,1,4,6\}$ are the only ones that meet the bound $\binom{\vert A\vert}{2} \geq N$ with equality. Completeness is required for OP's purpose. | |
| S Jan 8, 2015 at 12:49 | history | suggested | Ben Barber | CC BY-SA 3.0 |
tag and rewrite
|
| Jan 8, 2015 at 12:35 | review | Suggested edits | |||
| S Jan 8, 2015 at 12:49 | |||||
| Jan 8, 2015 at 9:27 | comment | added | Włodzimierz Holsztyński | What does the phrase naively prove mean? Does it mean prove? | |
| Jan 8, 2015 at 8:15 | comment | added | The Masked Avenger | Try Golomb rulers. | |
| S Jan 8, 2015 at 7:08 | history | suggested | cmn1 | CC BY-SA 3.0 |
Formatting organizing, Shortening title formatting
|
| Jan 8, 2015 at 6:31 | review | Suggested edits | |||
| S Jan 8, 2015 at 7:08 | |||||
| Jan 8, 2015 at 4:51 | review | Close votes | |||
| Jan 8, 2015 at 13:26 | |||||
| Jan 8, 2015 at 4:18 | history | asked | Qin Jianbin | CC BY-SA 3.0 |