Timeline for Size of sets with complete double
Current License: CC BY-SA 4.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18, 2021 at 11:35 | answer | added | Jukka Kohonen | timeline score: 4 | |
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Nov 28, 2019 at 10:04 | comment | added | Oliver Roche-Newton | Here is a closely related question which may be of interest. Perhaps Lucia's argument below can give a non-trivial improvement there too? mathoverflow.net/questions/323294/… | |
| Nov 1, 2019 at 13:13 | comment | added | Hailong Dao | Sure, I will do that. We probably would just refer to this question and answers in the example. Will probably take a few months before the paper is ready though. | |
| Nov 1, 2019 at 12:54 | comment | added | Lucia | If you eventually write up your examples, please do link them here. I'd be curious to see how such problems come up in commutative algebra. | |
| Nov 1, 2019 at 12:43 | comment | added | Hailong Dao | @Lucia: this arose when I tried to estimate certain algebraic invariants for a class of examples. So your answer (and everyone's contributions) are very helpful. Thanks. I am not sure if more could be done. It looks like a precise answer is not possible, and I don't really need very precise estimates, just to say: "for this class of examples, this invariant is hard to compute, but some rough estimates exist". | |
| Nov 1, 2019 at 12:39 | vote | accept | Hailong Dao | ||
| Nov 1, 2019 at 9:53 | comment | added | Lucia | Did this problem occur in some context in your work, or was it largely curiosity? My answer settles your Question 2 in the negative. Please let me know if you find anything there unclear, or if you were looking for something more. | |
| Oct 29, 2019 at 21:13 | history | edited | Lucia |
edited tags
|
|
| Oct 29, 2019 at 21:12 | answer | added | Lucia | timeline score: 11 | |
| Oct 21, 2019 at 6:36 | comment | added | Seva | "Perhaps one needs to really study the techniques there." - Absolutely. | |
| Oct 21, 2019 at 0:47 | comment | added | Hailong Dao | @Seva: I looked at some literature on additive bases, and my question can be translated to basis for $2n$ but lies inside $[n]$. Unfortunately no paper that I came across seemed to address this particular problem, and all the current records use elements in the interval $[n+1, 2n]$, which does not help immediately. Perhaps one needs to really study the techniques there. | |
| Oct 20, 2019 at 17:09 | comment | added | Seva | Here is yet another construction which gives $|S|=2(1+o(1))\sqrt{2n}$, at least for certain values of $n$. Suppose that $n=2^{m}$ with $m$ odd. Let $S=\{0\}\cup S_0\cup S_1$, where $S_0$ is the set of numbers in $[1,n]$ with all non-zero binary digits in the "even positions", and $S_1$ is the set of numbers in $[1,n]$ with all non-zero binary digits in the "odd positions". It is quite obvious that $S+S$ is the subset sum set of the set $\{0,1,2,4,\dotsc,2^m\}$, which is the interval $[0,2^{m+1}]=[0,2n]$. Also, for $m$ odd, we have $|S_0|=|S_1|=2^{(m+1)/2}$, whence $|S|=2\sqrt{2n}+1$. | |
| Oct 20, 2019 at 15:30 | comment | added | Hailong Dao | @Seva: that looks very relevant, thanks. | |
| Oct 20, 2019 at 13:58 | comment | added | Seva | The term to google is additive basis, or maybe try additive basis for interval. | |
| Oct 20, 2019 at 13:07 | answer | added | Aaron Meyerowitz | timeline score: 3 | |
| Oct 20, 2019 at 6:07 | comment | added | Hailong Dao | What the heck is going on at $n=31$? | |
| Oct 20, 2019 at 5:45 | answer | added | RobPratt | timeline score: 8 | |
| Oct 20, 2019 at 5:29 | comment | added | Hailong Dao | @RobPratt: thanks, that's great! Did you use any special algorithm/computer? I imagine a brute force search will get large very quickly. | |
| Oct 20, 2019 at 5:19 | comment | added | RobPratt | Here are the values of $m(n)$ for $n \in\{1,\dots,50\}$: 2 ,3 ,4 ,4 ,5 ,5 ,6 ,6 ,7 ,7 ,8 ,8 ,8 ,9 ,9 ,9 ,10 ,10 ,10 ,10 ,11 ,11 ,12 ,12 ,12 ,12 ,12 ,13 ,13 ,13 ,14 ,13 ,14 ,14 ,14 ,14 ,15 ,15 ,15 ,15 ,16 ,16 ,16 ,16 ,16 ,16 ,17 ,17 ,17 ,17. It doesn't seem to be in the OEIS. | |
| Oct 20, 2019 at 4:57 | history | edited | Hailong Dao | CC BY-SA 4.0 |
added 51 characters in body; edited title
|
| Oct 20, 2019 at 4:49 | comment | added | Gerry Myerson | OK, so, that's taking $d$ roughly $\sqrt{n/2}$. | |
| Oct 20, 2019 at 4:45 | comment | added | Hailong Dao | So it is about $2d+n/d$ which minimizes at $2\sqrt{2n}$! | |
| Oct 20, 2019 at 4:44 | comment | added | Gerry Myerson | Does it? $\sqrt n$ up to $d$, $\sqrt n$ down to $n-d$, and $\sqrt n$ between $d$ and $n-d$, I thought. | |
| Oct 20, 2019 at 4:41 | comment | added | Hailong Dao | I think that gets us to $2\sqrt{2n}$ actually. | |
| Oct 20, 2019 at 3:12 | comment | added | Gerry Myerson | Never mind, I miscalculated again. How about everything from zero to $d$, multiples of $d$ up to $n-d$, and everything from $n-d$ to $n$? That's $3\sqrt n$, asymptotically. | |
| Oct 19, 2019 at 22:00 | comment | added | Hailong Dao | @GerryMyerson: Can you say more on that modification? | |
| Oct 19, 2019 at 21:55 | comment | added | Gerry Myerson | Yes, you're right. A modification gets $2\sqrt2\sqrt n$ asymptotically, which isn't good enough. | |
| Oct 19, 2019 at 21:47 | comment | added | Hailong Dao | @GerryMyerson: I don't think so, if I understood your comment right. It would be hard to get things in the range $[2n-d...2n]$. | |
| Oct 19, 2019 at 21:43 | comment | added | Gerry Myerson | Don't you get $2\sqrt n$ asymptotically by taking everything from zero to $d$, the integer part of $\sqrt n$, and then all multiples of $d$ up to $n$? | |
| Oct 19, 2019 at 18:15 | history | edited | YCor |
edited tags
|
|
| Oct 19, 2019 at 18:03 | history | asked | Hailong Dao | CC BY-SA 4.0 |