Sets A such that A+A contains the largest set [0,1,..,t]Upper bound for size of subsets of a finite group...
Sets A such that A+A contains the largest set [0,1,..,t]
Upper bound for size of subsets of a finite group that contains a sum-full setCovering the integers by two kinds of three-element sets (IMO Shortlist 2001 problem C4): extensions and generalizations?Cliques in the Paley graph and a problem of SarkozyA generalization of the SET problemMinimal size of subsets $A,B$ in a finite group $G$ such that $AB=G$Integer solution to special system of linear equationsDoes the asymptotic formula for Partitions into parts <c exist?A set in Z/nZ which contains two elements, one of which is a small multiple of the otherWhat is the smallest cardinality of a set A whose difference A-A contains $n$ consequtive integer numbers?Reference Request: Waring's problem for different polynomials
$begingroup$
I look for a reference for the following problem.
Given an integer $k$, find a set $Asubsetmathbb{N}$ with $|A|=k$
that maximizes $t$ such that $left[0,1,..,tright]subset A+A$.
nt.number-theory co.combinatorics additive-combinatorics
edited 6 hours ago
Lucia
36.2k5 gold badges155 silver badges184 bronze badges
asked 9 hours ago
Pascal OchemPascal Ochem
1555 bronze badges
$endgroup$
add a comment |
$begingroup$
I look for a reference for the following problem.
Given an integer $k$, find a set $Asubsetmathbb{N}$ with $|A|=k$
that maximizes $t$ such that $left[0,1,..,tright]subset A+A$.
nt.number-theory co.combinatorics additive-combinatorics
edited 6 hours ago
Lucia
36.2k5 gold badges155 silver badges184 bronze badges
asked 9 hours ago
Pascal OchemPascal Ochem
1555 bronze badges
$endgroup$
$begingroup$
For low numbers:$$k=1, t=0: {0}$$ $$k=2, t=2: {0,1}$$ $$k=3, t=4: {0,1,2} text{ or } {0,1,3}$$ $$k=4, t=8: {0,1,3,4}$$
$endgroup$
– Matt F.
7 hours ago
2
$begingroup$
$$k=5, t=12: {0,1,3,5,6}$$Also, Oeis.org/A126684 can be used to find lower bounds for $t$. However, none of its OEIS cross-references begin with $0,2,4,8,12$, and none of the OEIS sequences beginning $0,2,4,8,12$ look promising -- so existing literature may have little to say on the sequence in the question.
$endgroup$
– Matt F.
6 hours ago
add a comment |
$begingroup$
I look for a reference for the following problem.
Given an integer $k$, find a set $Asubsetmathbb{N}$ with $|A|=k$
that maximizes $t$ such that $left[0,1,..,tright]subset A+A$.
nt.number-theory co.combinatorics additive-combinatorics
edited 6 hours ago
Lucia
36.2k5 gold badges155 silver badges184 bronze badges
asked 9 hours ago
Pascal OchemPascal Ochem
1555 bronze badges
$endgroup$
I look for a reference for the following problem.
Given an integer $k$, find a set $Asubsetmathbb{N}$ with $|A|=k$
that maximizes $t$ such that $left[0,1,..,tright]subset A+A$.
nt.number-theory co.combinatorics additive-combinatorics
nt.number-theory co.combinatorics additive-combinatorics
edited 6 hours ago
Lucia
36.2k5 gold badges155 silver badges184 bronze badges
asked 9 hours ago
Pascal OchemPascal Ochem
1555 bronze badges
edited 6 hours ago
Lucia
36.2k5 gold badges155 silver badges184 bronze badges
asked 9 hours ago
Pascal OchemPascal Ochem
1555 bronze badges
edited 6 hours ago
Lucia
36.2k5 gold badges155 silver badges184 bronze badges
edited 6 hours ago
Lucia
36.2k5 gold badges155 silver badges184 bronze badges
edited 6 hours ago
Lucia
36.2k5 gold badges155 silver badges184 bronze badges
36.2k5 gold badges155 silver badges184 bronze badges
asked 9 hours ago
Pascal OchemPascal Ochem
1555 bronze badges
asked 9 hours ago
Pascal OchemPascal Ochem
1555 bronze badges
asked 9 hours ago
Pascal OchemPascal Ochem
1555 bronze badges
1555 bronze badges
$begingroup$
For low numbers:$$k=1, t=0: {0}$$ $$k=2, t=2: {0,1}$$ $$k=3, t=4: {0,1,2} text{ or } {0,1,3}$$ $$k=4, t=8: {0,1,3,4}$$
$endgroup$
– Matt F.
7 hours ago
2
$begingroup$
$$k=5, t=12: {0,1,3,5,6}$$Also, Oeis.org/A126684 can be used to find lower bounds for $t$. However, none of its OEIS cross-references begin with $0,2,4,8,12$, and none of the OEIS sequences beginning $0,2,4,8,12$ look promising -- so existing literature may have little to say on the sequence in the question.
$endgroup$
– Matt F.
6 hours ago
add a comment |
$begingroup$
For low numbers:$$k=1, t=0: {0}$$ $$k=2, t=2: {0,1}$$ $$k=3, t=4: {0,1,2} text{ or } {0,1,3}$$ $$k=4, t=8: {0,1,3,4}$$
$endgroup$
– Matt F.
7 hours ago
2
$begingroup$
$$k=5, t=12: {0,1,3,5,6}$$Also, Oeis.org/A126684 can be used to find lower bounds for $t$. However, none of its OEIS cross-references begin with $0,2,4,8,12$, and none of the OEIS sequences beginning $0,2,4,8,12$ look promising -- so existing literature may have little to say on the sequence in the question.
$endgroup$
– Matt F.
6 hours ago
$begingroup$
For low numbers:$$k=1, t=0: {0}$$ $$k=2, t=2: {0,1}$$ $$k=3, t=4: {0,1,2} text{ or } {0,1,3}$$ $$k=4, t=8: {0,1,3,4}$$
$endgroup$
– Matt F.
7 hours ago
$begingroup$
For low numbers:$$k=1, t=0: {0}$$ $$k=2, t=2: {0,1}$$ $$k=3, t=4: {0,1,2} text{ or } {0,1,3}$$ $$k=4, t=8: {0,1,3,4}$$
$endgroup$
– Matt F.
7 hours ago
2
2
$begingroup$
$$k=5, t=12: {0,1,3,5,6}$$Also, Oeis.org/A126684 can be used to find lower bounds for $t$. However, none of its OEIS cross-references begin with $0,2,4,8,12$, and none of the OEIS sequences beginning $0,2,4,8,12$ look promising -- so existing literature may have little to say on the sequence in the question.
$endgroup$
– Matt F.
6 hours ago
$begingroup$
$$k=5, t=12: {0,1,3,5,6}$$Also, Oeis.org/A126684 can be used to find lower bounds for $t$. However, none of its OEIS cross-references begin with $0,2,4,8,12$, and none of the OEIS sequences beginning $0,2,4,8,12$ look promising -- so existing literature may have little to say on the sequence in the question.
$endgroup$
– Matt F.
6 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
A table of values for these $t$ are given in the introduction Graham and Sloane's On Additive Bases and Harmonius Graphs (your sequence corresponds to $n_beta(k)$ in their notation). Graham and Sloane also give some references to previous work with this sequence, both under the name of "interval basis" (or Abschnittsbasis), going back to a paper in German from Rohrbach in the 1930's, and under the name of "The Postage Stamp Problem".
This is sequence A001212 in the OEIS, which has additional references.
answered 6 hours ago
Kevin P. CostelloKevin P. Costello
5,0361 gold badge20 silver badges32 bronze badges
$endgroup$
$begingroup$
Glad you found this or knew it! Now I see why I missed it...I got confused by not seeing 0's and thinking that the postage stamp problem was about two-dimensional configurations of stamps instead.
$endgroup$
– Matt F.
5 hours ago
add a comment |
$begingroup$
This is related to ``thin additive bases" of order $2$. Clearly $t$ cannot be larger than $k(k+1)/2$. It is also possible to give examples where $t$ grows quadratically. Take $A=A_0 cup A_1$ where $A_0$ contains all integers below
$t$ with binary expansion $sum_{j} epsilon_j 2^j$ with $epsilon_j= 0$ unless $j$ is even, and $A_1$ consists of numbers with binary digits $epsilon_j=0$ unless $j$ is odd. Then $A$ has $O(sqrt{t})$ elements in it; or alternatively $tge Ck^2$ for some constant $C>0$. See for example this paper of Blomer which has other references.
answered 6 hours ago
LuciaLucia
36.2k5 gold badges155 silver badges184 bronze badges
$endgroup$
2
$begingroup$
or simply take $A={0,1,ldots,m-1}cup {m,2m,3m,ldots,m^2}$ for $m=lfloor k/2 rfloor$
$endgroup$
– Fedor Petrov
6 hours ago
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "504"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f337939%2fsets-a-such-that-aa-contains-the-largest-set-0-1-t%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
A table of values for these $t$ are given in the introduction Graham and Sloane's On Additive Bases and Harmonius Graphs (your sequence corresponds to $n_beta(k)$ in their notation). Graham and Sloane also give some references to previous work with this sequence, both under the name of "interval basis" (or Abschnittsbasis), going back to a paper in German from Rohrbach in the 1930's, and under the name of "The Postage Stamp Problem".
This is sequence A001212 in the OEIS, which has additional references.
answered 6 hours ago
Kevin P. CostelloKevin P. Costello
5,0361 gold badge20 silver badges32 bronze badges
$endgroup$
$begingroup$
Glad you found this or knew it! Now I see why I missed it...I got confused by not seeing 0's and thinking that the postage stamp problem was about two-dimensional configurations of stamps instead.
$endgroup$
– Matt F.
5 hours ago
add a comment |
$begingroup$
A table of values for these $t$ are given in the introduction Graham and Sloane's On Additive Bases and Harmonius Graphs (your sequence corresponds to $n_beta(k)$ in their notation). Graham and Sloane also give some references to previous work with this sequence, both under the name of "interval basis" (or Abschnittsbasis), going back to a paper in German from Rohrbach in the 1930's, and under the name of "The Postage Stamp Problem".
This is sequence A001212 in the OEIS, which has additional references.
answered 6 hours ago
Kevin P. CostelloKevin P. Costello
5,0361 gold badge20 silver badges32 bronze badges
$endgroup$
$begingroup$
Glad you found this or knew it! Now I see why I missed it...I got confused by not seeing 0's and thinking that the postage stamp problem was about two-dimensional configurations of stamps instead.
$endgroup$
– Matt F.
5 hours ago
add a comment |
$begingroup$
A table of values for these $t$ are given in the introduction Graham and Sloane's On Additive Bases and Harmonius Graphs (your sequence corresponds to $n_beta(k)$ in their notation). Graham and Sloane also give some references to previous work with this sequence, both under the name of "interval basis" (or Abschnittsbasis), going back to a paper in German from Rohrbach in the 1930's, and under the name of "The Postage Stamp Problem".
This is sequence A001212 in the OEIS, which has additional references.
answered 6 hours ago
Kevin P. CostelloKevin P. Costello
5,0361 gold badge20 silver badges32 bronze badges
$endgroup$
A table of values for these $t$ are given in the introduction Graham and Sloane's On Additive Bases and Harmonius Graphs (your sequence corresponds to $n_beta(k)$ in their notation). Graham and Sloane also give some references to previous work with this sequence, both under the name of "interval basis" (or Abschnittsbasis), going back to a paper in German from Rohrbach in the 1930's, and under the name of "The Postage Stamp Problem".
This is sequence A001212 in the OEIS, which has additional references.
answered 6 hours ago
Kevin P. CostelloKevin P. Costello
5,0361 gold badge20 silver badges32 bronze badges
answered 6 hours ago
Kevin P. CostelloKevin P. Costello
5,0361 gold badge20 silver badges32 bronze badges
answered 6 hours ago
Kevin P. CostelloKevin P. Costello
5,0361 gold badge20 silver badges32 bronze badges
answered 6 hours ago
Kevin P. CostelloKevin P. Costello
5,0361 gold badge20 silver badges32 bronze badges
5,0361 gold badge20 silver badges32 bronze badges
$begingroup$
Glad you found this or knew it! Now I see why I missed it...I got confused by not seeing 0's and thinking that the postage stamp problem was about two-dimensional configurations of stamps instead.
$endgroup$
– Matt F.
5 hours ago
add a comment |
$begingroup$
Glad you found this or knew it! Now I see why I missed it...I got confused by not seeing 0's and thinking that the postage stamp problem was about two-dimensional configurations of stamps instead.
$endgroup$
– Matt F.
5 hours ago
$begingroup$
Glad you found this or knew it! Now I see why I missed it...I got confused by not seeing 0's and thinking that the postage stamp problem was about two-dimensional configurations of stamps instead.
$endgroup$
– Matt F.
5 hours ago
$begingroup$
Glad you found this or knew it! Now I see why I missed it...I got confused by not seeing 0's and thinking that the postage stamp problem was about two-dimensional configurations of stamps instead.
$endgroup$
– Matt F.
5 hours ago
add a comment |
$begingroup$
This is related to ``thin additive bases" of order $2$. Clearly $t$ cannot be larger than $k(k+1)/2$. It is also possible to give examples where $t$ grows quadratically. Take $A=A_0 cup A_1$ where $A_0$ contains all integers below
$t$ with binary expansion $sum_{j} epsilon_j 2^j$ with $epsilon_j= 0$ unless $j$ is even, and $A_1$ consists of numbers with binary digits $epsilon_j=0$ unless $j$ is odd. Then $A$ has $O(sqrt{t})$ elements in it; or alternatively $tge Ck^2$ for some constant $C>0$. See for example this paper of Blomer which has other references.
answered 6 hours ago
LuciaLucia
36.2k5 gold badges155 silver badges184 bronze badges
$endgroup$
2
$begingroup$
or simply take $A={0,1,ldots,m-1}cup {m,2m,3m,ldots,m^2}$ for $m=lfloor k/2 rfloor$
$endgroup$
– Fedor Petrov
6 hours ago
add a comment |
$begingroup$
This is related to ``thin additive bases" of order $2$. Clearly $t$ cannot be larger than $k(k+1)/2$. It is also possible to give examples where $t$ grows quadratically. Take $A=A_0 cup A_1$ where $A_0$ contains all integers below
$t$ with binary expansion $sum_{j} epsilon_j 2^j$ with $epsilon_j= 0$ unless $j$ is even, and $A_1$ consists of numbers with binary digits $epsilon_j=0$ unless $j$ is odd. Then $A$ has $O(sqrt{t})$ elements in it; or alternatively $tge Ck^2$ for some constant $C>0$. See for example this paper of Blomer which has other references.
answered 6 hours ago
LuciaLucia
36.2k5 gold badges155 silver badges184 bronze badges
$endgroup$
2
$begingroup$
or simply take $A={0,1,ldots,m-1}cup {m,2m,3m,ldots,m^2}$ for $m=lfloor k/2 rfloor$
$endgroup$
– Fedor Petrov
6 hours ago
add a comment |
$begingroup$
This is related to ``thin additive bases" of order $2$. Clearly $t$ cannot be larger than $k(k+1)/2$. It is also possible to give examples where $t$ grows quadratically. Take $A=A_0 cup A_1$ where $A_0$ contains all integers below
$t$ with binary expansion $sum_{j} epsilon_j 2^j$ with $epsilon_j= 0$ unless $j$ is even, and $A_1$ consists of numbers with binary digits $epsilon_j=0$ unless $j$ is odd. Then $A$ has $O(sqrt{t})$ elements in it; or alternatively $tge Ck^2$ for some constant $C>0$. See for example this paper of Blomer which has other references.
answered 6 hours ago
LuciaLucia
36.2k5 gold badges155 silver badges184 bronze badges
$endgroup$
This is related to ``thin additive bases" of order $2$. Clearly $t$ cannot be larger than $k(k+1)/2$. It is also possible to give examples where $t$ grows quadratically. Take $A=A_0 cup A_1$ where $A_0$ contains all integers below
$t$ with binary expansion $sum_{j} epsilon_j 2^j$ with $epsilon_j= 0$ unless $j$ is even, and $A_1$ consists of numbers with binary digits $epsilon_j=0$ unless $j$ is odd. Then $A$ has $O(sqrt{t})$ elements in it; or alternatively $tge Ck^2$ for some constant $C>0$. See for example this paper of Blomer which has other references.
answered 6 hours ago
LuciaLucia
36.2k5 gold badges155 silver badges184 bronze badges
answered 6 hours ago
LuciaLucia
36.2k5 gold badges155 silver badges184 bronze badges
answered 6 hours ago
LuciaLucia
36.2k5 gold badges155 silver badges184 bronze badges
answered 6 hours ago
LuciaLucia
36.2k5 gold badges155 silver badges184 bronze badges
36.2k5 gold badges155 silver badges184 bronze badges
2
$begingroup$
or simply take $A={0,1,ldots,m-1}cup {m,2m,3m,ldots,m^2}$ for $m=lfloor k/2 rfloor$
$endgroup$
– Fedor Petrov
6 hours ago
add a comment |
2
$begingroup$
or simply take $A={0,1,ldots,m-1}cup {m,2m,3m,ldots,m^2}$ for $m=lfloor k/2 rfloor$
$endgroup$
– Fedor Petrov
6 hours ago
2
2
$begingroup$
or simply take $A={0,1,ldots,m-1}cup {m,2m,3m,ldots,m^2}$ for $m=lfloor k/2 rfloor$
$endgroup$
– Fedor Petrov
6 hours ago
$begingroup$
or simply take $A={0,1,ldots,m-1}cup {m,2m,3m,ldots,m^2}$ for $m=lfloor k/2 rfloor$
$endgroup$
– Fedor Petrov
6 hours ago
add a comment |
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f337939%2fsets-a-such-that-aa-contains-the-largest-set-0-1-t%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
For low numbers:$$k=1, t=0: {0}$$ $$k=2, t=2: {0,1}$$ $$k=3, t=4: {0,1,2} text{ or } {0,1,3}$$ $$k=4, t=8: {0,1,3,4}$$
$endgroup$
– Matt F.
7 hours ago
2
$begingroup$
$$k=5, t=12: {0,1,3,5,6}$$Also, Oeis.org/A126684 can be used to find lower bounds for $t$. However, none of its OEIS cross-references begin with $0,2,4,8,12$, and none of the OEIS sequences beginning $0,2,4,8,12$ look promising -- so existing literature may have little to say on the sequence in the question.
$endgroup$
– Matt F.
6 hours ago