I'm looking for a set $S \subseteq \mathbb N$ with the following property: There is an infinite set of linear shifts $L \subseteq \mathbb N$ and a finite set $F \subseteq \mathbb N$, such that $S$ is equal to the disjoint union of $F$ and $\{s+l:s \in S\}$ for each $l \in L$.

If we drop the requirement that $L$ is infinite, then $S=\{0,1,2,3,\dots\}$ works (with $L=\{1\}$ and $F=\{0\}$).

(In essence, I'm looking for a discrete fractal, a subset of $\mathbb N$ that is made up of infinitely many copies of itself (minus a finite number of points).)

  • $\begingroup$ Do you mean the usual disjoint union or simply that F and l + S are always disjoint disjoint? $\endgroup$ – William Elliot May 15 '18 at 20:05
  • $\begingroup$ @WilliamElliot that l+S are always disjoint from $F$ and each other. $\endgroup$ – PyRulez May 15 '18 at 20:09
  • $\begingroup$ FYI - You are misusing "fractal" here. Self-similarity is a technique for building fractals, but it is not what fractals are. $\endgroup$ – Paul Sinclair May 16 '18 at 16:20
  • $\begingroup$ Incidentally, this question becomes a little more interesting (though also with several trivial answers) if you allow S to contain not just exact copies of itself, but 'scaled' copies of itself; that actually maps more directly onto the traditional way of looking at fractals like the Sierpinski gasket. Since 'shrinking' a set in $\mathbb{Z}$ corresponds to making it less dense, it corresponds most directly to the set $d\cdot S$ for some $d$. (cont.) $\endgroup$ – Steven Stadnicki May 16 '18 at 19:38
  • 1
    $\begingroup$ This means that you should probably look at $S$ which are the disjoint union of $F$ and the sets $S_i=\ell_i+d_i\cdot S = \{\ell_i+d_i\cdot s : s\in S\}$, for some set of ordered pairs $\langle d_i, \ell_i\rangle$ representing the 'scales' and 'offsets' of the copies of $S$ within $S$ itself. $\endgroup$ – Steven Stadnicki May 16 '18 at 19:41

Such a set cannot exist, given the requirement that the union be disjoint; in fact, it cannot even exist with $|L|\gt 1$.

Let $d_L$ be the GCD of $L$; then by the solution to the Frobenius problem, there exists some $N_0$ such that $\forall n\geq N_0, n\cdot d_L$ can be expressed as a linear combination of elements in $L$. Now, fix the choice of some element $s$ of $S$ (for instance, any of the members of $F$ will do); then this implies that every element $s+n\cdot d_L, n\geq N_0$ must be in $S$.

Now, choose two elements $\ell_1, \ell_2\in L$. Then $(s+N_0\cdot d_L+\ell_1)\in S$ (because this is $s+n\cdot d_L$ for an $n\geq N_0$), so $(s+N_0\cdot d_L+\ell_1+\ell_2)\in S+\ell_2$. Similarly, since $(s+N_0\cdot d_L+\ell_2)\in S$, $()s+N_0\cdot d_L+\ell_1+\ell_2)\in S+\ell_1$. But since this element is in $S+\ell_1$ and $S+\ell_2$, it's impossible for the union $\bigcup\{S+\ell: \ell\in L\}$ to be disjoint.

  • 1
    $\begingroup$ I had just worked up a similar solution, then realized a simpler variation works: By the union requirement $S + \ell_1 \subset S \implies (S + \ell_1) + \ell_2 \subset S + \ell_2$, and similarly $(S + \ell_2) + \ell_1 \subset S + \ell_1$. Since these two sets are in fact the same, it cannot be that $S+\ell_1 \cap S + \ell_2 = \emptyset$. $\endgroup$ – Paul Sinclair May 17 '18 at 10:11

Edit: based on the final sentence in the post, I think Steven Stadnicki is correct that I have the wrong interpretation, but I will leave this answer anyway in case something useful can be gleaned from it.

If $L$ contains $2$ members $a, b$, then you are requiring that $S + a \cap F = \emptyset$ and $S + a \cup F = S$, so $S + a = S \setminus F$. But the same thing is true of $S + b$, so $S + a = S + b = S \setminus F$.

Since $S \subset \Bbb N$, it has a least element $s$, and therefore the least element of $S + a$ is $s + a$, and of $S + b$ is $s+b$. But since these two sets are the same, $s + a = s + b$, and therefore $a = b$.

I.e. for any three non-empty sets $S, L, F$ with these properties, $L$ can have only one element. An infinite $L$ is impossible.

  • $\begingroup$ I think OP's intention is that $S=\cup\{F, \{s+\ell: s\in S, \ell\in L\}\}$, rather than that $\forall \ell\in L, S=F\cup\{s+\ell: s\in S\}$, but that's not entirely clear from the question. $\endgroup$ – Steven Stadnicki May 16 '18 at 4:15
  • $\begingroup$ @StevenStadnicki that's correct. Sorry if the question was vague. $\endgroup$ – PyRulez May 16 '18 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.