How many arithmetic progressions are necessary to form an arbitrary subset of $mathbb{Z}_n$?
$begingroup$
I couldn't find a way to ask the question in under 150 characters, so I've rewritten it in a way that makes more sense.
Given an integer $n$, what is the minimum $k$ such that for any subset $X subseteq mathbb{Z}/nmathbb{Z}$, there exists a set of order at most $k$ of arithmetic progressions whose union is exactly equal to $X$?
I am interested in the group ($mathbb{Z}/n mathbb{Z}$, +), so I would like to consider an arithmetic progression to be a set ${a, a+d, a+2d, dots, a+kd}$, where addition is calculated mod $n$. For example, in $mathbb{Z}/12 mathbb{Z}$, I would consider $9, 11, 1, 3$ to be an arithmetic progression of length 4.
To give some examples of what I am thinking about, I will consider some subsets of $mathbb{Z}/24 mathbb{Z}$. The set ${0, 1, 2, dots, 11}$ can be considered to be a single arithmetic progression. The set ${0,3,4,5,20,22}$ can be considered to the the union of the two arithmetic progressions $(3,4,5)$ and $(20,22,0)$. The set ${1,2,4,8,16}$ is not a union of two arithmetic progressions, but we can consider it to the union of three arithmetic progressions, namely $(1,2)$, $(2,4)$, and $(8,16)$. What I have shown is that given some subset of $mathbb{Z}/24 mathbb{Z}$, we may need three (or possibly more) arithmetic progressions in order to form a union exactly equal to that subset. So for $n=24$, $k geq 3$.
Is there a general way to calculate $k$ for general $n$? Are there any results or conjectures that are related to this kind of question in any way?
Any help would be appreciated. Thank you.
combinatorics number-theory
asked Dec 24 '18 at 5:29
Peter BradshawPeter Bradshaw
428211
$endgroup$
add a comment |
$begingroup$
I couldn't find a way to ask the question in under 150 characters, so I've rewritten it in a way that makes more sense.
Given an integer $n$, what is the minimum $k$ such that for any subset $X subseteq mathbb{Z}/nmathbb{Z}$, there exists a set of order at most $k$ of arithmetic progressions whose union is exactly equal to $X$?
I am interested in the group ($mathbb{Z}/n mathbb{Z}$, +), so I would like to consider an arithmetic progression to be a set ${a, a+d, a+2d, dots, a+kd}$, where addition is calculated mod $n$. For example, in $mathbb{Z}/12 mathbb{Z}$, I would consider $9, 11, 1, 3$ to be an arithmetic progression of length 4.
To give some examples of what I am thinking about, I will consider some subsets of $mathbb{Z}/24 mathbb{Z}$. The set ${0, 1, 2, dots, 11}$ can be considered to be a single arithmetic progression. The set ${0,3,4,5,20,22}$ can be considered to the the union of the two arithmetic progressions $(3,4,5)$ and $(20,22,0)$. The set ${1,2,4,8,16}$ is not a union of two arithmetic progressions, but we can consider it to the union of three arithmetic progressions, namely $(1,2)$, $(2,4)$, and $(8,16)$. What I have shown is that given some subset of $mathbb{Z}/24 mathbb{Z}$, we may need three (or possibly more) arithmetic progressions in order to form a union exactly equal to that subset. So for $n=24$, $k geq 3$.
Is there a general way to calculate $k$ for general $n$? Are there any results or conjectures that are related to this kind of question in any way?
Any help would be appreciated. Thank you.
combinatorics number-theory
asked Dec 24 '18 at 5:29
Peter BradshawPeter Bradshaw
428211
$endgroup$
$begingroup$
It might give a first idea to write down where the first jumps in $k$ occur, up to $n=12$ or so.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
1
$begingroup$
Conjecture: An $X$ with maximal $k$ is given by the first $k+1$ entries of $(0,1,3,6,10,15, ...)$, as soon as the distance of the last entry to $n$ is greater than all distances that occur before. This gives $k$ to be the largest number such that $frac{k(k+1)}{2} +k le n$, which is $k = lfloor sqrt{2n+frac94} -frac32 rfloor$.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
add a comment |
$begingroup$
I couldn't find a way to ask the question in under 150 characters, so I've rewritten it in a way that makes more sense.
Given an integer $n$, what is the minimum $k$ such that for any subset $X subseteq mathbb{Z}/nmathbb{Z}$, there exists a set of order at most $k$ of arithmetic progressions whose union is exactly equal to $X$?
I am interested in the group ($mathbb{Z}/n mathbb{Z}$, +), so I would like to consider an arithmetic progression to be a set ${a, a+d, a+2d, dots, a+kd}$, where addition is calculated mod $n$. For example, in $mathbb{Z}/12 mathbb{Z}$, I would consider $9, 11, 1, 3$ to be an arithmetic progression of length 4.
To give some examples of what I am thinking about, I will consider some subsets of $mathbb{Z}/24 mathbb{Z}$. The set ${0, 1, 2, dots, 11}$ can be considered to be a single arithmetic progression. The set ${0,3,4,5,20,22}$ can be considered to the the union of the two arithmetic progressions $(3,4,5)$ and $(20,22,0)$. The set ${1,2,4,8,16}$ is not a union of two arithmetic progressions, but we can consider it to the union of three arithmetic progressions, namely $(1,2)$, $(2,4)$, and $(8,16)$. What I have shown is that given some subset of $mathbb{Z}/24 mathbb{Z}$, we may need three (or possibly more) arithmetic progressions in order to form a union exactly equal to that subset. So for $n=24$, $k geq 3$.
Is there a general way to calculate $k$ for general $n$? Are there any results or conjectures that are related to this kind of question in any way?
Any help would be appreciated. Thank you.
combinatorics number-theory
asked Dec 24 '18 at 5:29
Peter BradshawPeter Bradshaw
428211
$endgroup$
I couldn't find a way to ask the question in under 150 characters, so I've rewritten it in a way that makes more sense.
Given an integer $n$, what is the minimum $k$ such that for any subset $X subseteq mathbb{Z}/nmathbb{Z}$, there exists a set of order at most $k$ of arithmetic progressions whose union is exactly equal to $X$?
I am interested in the group ($mathbb{Z}/n mathbb{Z}$, +), so I would like to consider an arithmetic progression to be a set ${a, a+d, a+2d, dots, a+kd}$, where addition is calculated mod $n$. For example, in $mathbb{Z}/12 mathbb{Z}$, I would consider $9, 11, 1, 3$ to be an arithmetic progression of length 4.
To give some examples of what I am thinking about, I will consider some subsets of $mathbb{Z}/24 mathbb{Z}$. The set ${0, 1, 2, dots, 11}$ can be considered to be a single arithmetic progression. The set ${0,3,4,5,20,22}$ can be considered to the the union of the two arithmetic progressions $(3,4,5)$ and $(20,22,0)$. The set ${1,2,4,8,16}$ is not a union of two arithmetic progressions, but we can consider it to the union of three arithmetic progressions, namely $(1,2)$, $(2,4)$, and $(8,16)$. What I have shown is that given some subset of $mathbb{Z}/24 mathbb{Z}$, we may need three (or possibly more) arithmetic progressions in order to form a union exactly equal to that subset. So for $n=24$, $k geq 3$.
Is there a general way to calculate $k$ for general $n$? Are there any results or conjectures that are related to this kind of question in any way?
Any help would be appreciated. Thank you.
combinatorics number-theory
combinatorics number-theory
asked Dec 24 '18 at 5:29
Peter BradshawPeter Bradshaw
428211
asked Dec 24 '18 at 5:29
Peter BradshawPeter Bradshaw
428211
asked Dec 24 '18 at 5:29
Peter BradshawPeter Bradshaw
428211
asked Dec 24 '18 at 5:29
Peter BradshawPeter Bradshaw
428211
asked Dec 24 '18 at 5:29
Peter BradshawPeter Bradshaw
428211
428211
$begingroup$
It might give a first idea to write down where the first jumps in $k$ occur, up to $n=12$ or so.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
1
$begingroup$
Conjecture: An $X$ with maximal $k$ is given by the first $k+1$ entries of $(0,1,3,6,10,15, ...)$, as soon as the distance of the last entry to $n$ is greater than all distances that occur before. This gives $k$ to be the largest number such that $frac{k(k+1)}{2} +k le n$, which is $k = lfloor sqrt{2n+frac94} -frac32 rfloor$.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
add a comment |
$begingroup$
It might give a first idea to write down where the first jumps in $k$ occur, up to $n=12$ or so.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
1
$begingroup$
Conjecture: An $X$ with maximal $k$ is given by the first $k+1$ entries of $(0,1,3,6,10,15, ...)$, as soon as the distance of the last entry to $n$ is greater than all distances that occur before. This gives $k$ to be the largest number such that $frac{k(k+1)}{2} +k le n$, which is $k = lfloor sqrt{2n+frac94} -frac32 rfloor$.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
$begingroup$
It might give a first idea to write down where the first jumps in $k$ occur, up to $n=12$ or so.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
$begingroup$
It might give a first idea to write down where the first jumps in $k$ occur, up to $n=12$ or so.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
1
1
$begingroup$
Conjecture: An $X$ with maximal $k$ is given by the first $k+1$ entries of $(0,1,3,6,10,15, ...)$, as soon as the distance of the last entry to $n$ is greater than all distances that occur before. This gives $k$ to be the largest number such that $frac{k(k+1)}{2} +k le n$, which is $k = lfloor sqrt{2n+frac94} -frac32 rfloor$.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
$begingroup$
Conjecture: An $X$ with maximal $k$ is given by the first $k+1$ entries of $(0,1,3,6,10,15, ...)$, as soon as the distance of the last entry to $n$ is greater than all distances that occur before. This gives $k$ to be the largest number such that $frac{k(k+1)}{2} +k le n$, which is $k = lfloor sqrt{2n+frac94} -frac32 rfloor$.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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%2fmath.stackexchange.com%2fquestions%2f3050968%2fhow-many-arithmetic-progressions-are-necessary-to-form-an-arbitrary-subset-of%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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%2fmath.stackexchange.com%2fquestions%2f3050968%2fhow-many-arithmetic-progressions-are-necessary-to-form-an-arbitrary-subset-of%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$
It might give a first idea to write down where the first jumps in $k$ occur, up to $n=12$ or so.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54
1
$begingroup$
Conjecture: An $X$ with maximal $k$ is given by the first $k+1$ entries of $(0,1,3,6,10,15, ...)$, as soon as the distance of the last entry to $n$ is greater than all distances that occur before. This gives $k$ to be the largest number such that $frac{k(k+1)}{2} +k le n$, which is $k = lfloor sqrt{2n+frac94} -frac32 rfloor$.
$endgroup$
– Torsten Schoeneberg
Dec 24 '18 at 18:54