Woett's Blog

The subtraction game

June 26, 2014

In the subtraction game, two players start with a pile of chips and they alternate taking away any number $s_i$ (from a previously fixed set $S = \{s_1, \ldots, s_t\}$ of positive integers) of chips from the pile. If you can’t make a move anymore, because there are less chips left than the smallest member of $S$ , you lose. This game has been solved in the case $|S| = 2$ , but thus far hasn’t been solved in general when $|S| > 2$ , although some partial results are known. For example, it is known that for any set $S$ there exists an $m$ such that for large enough $n$ , if you start with $n$ chips, the question if this game is a win for Player $1$ only depends on $n \pmod m$ . That is, the sequence of $n$ such that Player $1$ wins if the starting pile consists of $n$ chips, is ultimately periodic. I think I found the period and the corresponding nimvalues (http://en.wikipedia.org/wiki/Nim-sequence) of the periodic parts, assuming $S = \{1, a, b\}$ . No explanation or anything, just stating what I think are the correct values. Maybe I’ll explain what the hell I’m talking about in a future post. Maybe not 😉

Let $b = c*(a+1) + k$ , where $c \ge 1$ and $0 \le k \le a$ . Then the periodic part of the nimsequence is as follows:

$01$ , if

– $a$ is odd
– $b$ is odd

$(01)^{b/2} (23)^{(a-1)/2} 2$ , if

– $a$ is odd
– $b$ is even

Notice: thus far we’ve handled all cases with $a$ odd. This was known before, check for example http://arxiv.org/pdf/1202.2986.pdf.

$(012)^c 3$ , if

– $a = 2$
– $k = 0$

$(01)^{a/2} 2$ , if

– $a$ is even
– $k \in \{1, a\}$

$((01)^{a/2} 2)^{c+1} (32)^{(k-1)/2}$ , if

– $a$ is even
– $k$ is odd
– $1 < k < a$

Note: now we handled all cases with $a$ even and $k$ odd.

$((01)^{a/2} 2)^c (01)^{a/2-1}2$ , if

– $a \ge 4$ is even
– $k = a - 2$

Note: and now we’re also done with $k \ge a - 2$ .

$(01)^{a/2} (23)^{a/2}$ , if

– $a$ is even
– $k = 0$
– $c = 1$

$(01012)^{c-1} (012)^2$ , if

– $a = 4$
– $k = 0$
– $c > 1$

And now we’re also completely done with $a = 4$ . All that’s left now is the case $a \ge 6$ even and $k < a-2$ even, where if $k = 0$ , $c > 1$ . We will split this case in three: either $k$ exactly equals $a - 2c - 2$ , or $k > a - 2c - 2$ , or $k < a - 2c - 2$ , and in this last case we have to distinguish between $k = 0$ or $k > 0$ . Here goes.

$2(01)^{a/2-1}$ , if

– $a \ge 6$ is even
– $k$ is even
– $k = a - 2c - 2$

$2(01)^{a/2-1} (2 (01)^{a/2})^{c - a/2 + k/2 + 1} (2(01)^{a/2 - 1})^{a/2 - k/2 - 1}$ , if

– $a \ge 6$ is even
– $k$ is even
– $a - 2c - 2 < k < a - 2$

$(23)^{a/2-c-1} 2(01)^c (2 (01)^{a/2 -1})^c 2(01)^c$ , if

– $a$ is even
– $k = 0$
– $k < a - 2c - 2$
– $c > 1$
– Using the fact that $k = 0$ , these last two assumptions can be written as: $1 < c < a/2 - 1$

$(23)^{a/2 - k/2 - c - 1} 2 (01)^{k/2 + c} (2 (01)^{a/2 - 1})^{c} 2 (01)^{k/2 + c}$ , if

– $a$ is even
– $k$ is even
– $0 < k < a - 2c - 2$

Posted in Uncategorized | Leave a Comment »

Sumsets not containing a power of two

June 26, 2012

Let $A = \{a_1, a_2, .. \}$ be an infinite set of positive integers under the following constraints:

1) $a_1 = 1$ .
2) For all $k$ we have: $a_k < a_{k+1} \le 2a_k + 1$ .

Let $n$ be a non-negative integer and let $S \subseteq \{0, 1, .., n\}$ be a set of non-negative integers containing $0$ . Define $S + S = \{x + y | x,y \in S\}$ . That is, since $S$ contains $0$ , the set $S + S$ is the set of all integers that can be written as a sum of at most two non-zero elements of $S$ . We now have the following theorem:

Theorem. If $(S + S) \cap A = \emptyset$ , then $|S| \le (n+j)/2$ , where $j$ is either $1$ or $2$ , according to whether the smallest element of $A$ larger than $n$ (which we shall call $a_{k+1}$ ) is even or odd.

In particular, if $|S| \ge n/2 + 1$ , then some power of two can be written as sum of at most two elements of $S$ . In Additive Number Theory: Inverse Problems and the Geometry of Sumsets (which is an awesome book, by the way!) this special case is proved and then used to prove the neat fact that if $S \subseteq \{1, 2, .., n\}$ and $|S| > n/3$ , then some power of two can be written as sum of at most four elements of $S$ . We will now prove the general version.

Proof. When $n \in A$ , then, for $i = 0, 1, .., \lfloor (n-1)/2 \rfloor$ , at most one of $i, n-i$ lies in $S$ (why does $n/2$ not lie in $S$ ?), so we then immediately have $|S| \le (n+1)/2$ . So we may assume that $n \notin A$ . Furthermore, for $n = 0$ , we obviously have $|S| \le (n+2)/2$ . Now assume that, for all $n' < n$ we have that the largest set $S' \subseteq \{0, 1, .., n'\}$ for which no $a_i$ is the sum of at most two elements of $S'$ , has cardinality at most $(n'+2)/2$ . We will use this induction hypothesis to prove our Theorem.

Case I. $a_{k+1}$ is even.

First some definitions:

Let $S \subseteq \{0, 1, .., n\}$ be a set such that no element of $A$ can be written as a sum of at most two elements of $S$ .
Let $k$ be such that $a_k < n < a_{k+1}$ .
Let $m$ be such that $n + m = a_{k+1}$ (note that $m = a_{k+1} - n \le a_{k+1} - a_k - 1 \le (a_{k+1}-1)/2 \le a_k < n$ ).
Let $S_0 = S \cap \{0, 1, .., m-1\}$ (on which we will use the induction hypothesis, which is allowed, since $m-1 < n$ ).
Let $S_{i-m+1} = S \cap \{i, a_{k+1} - i\}$ , for $i = m, m+1, .., a_{k+1}/2$ .

Now note that, for all relevant $i \ge 1$ , we get $|S_i| \le 1$ , while for $i = a_{k+1}/2$ we even know $|S_{i-m+1}| = 0$ (again, why?). What’s left is a direct computation.

$|S| = |S_0| + \displaystyle \sum_{i=1}^{a_{k+1}/2 - m} |S_{i}| \\ \le (m+1)/2 + a_{k+1}/2 - m \\ = a_{k+1}/2 - (m-1)/2 \\ = (n+1)/2$

Case II. $a_{k+1}$ is odd.

We carry over all definitions of Case I, with the exception of the fact that the sets $S_{i-m+1}$ are now defined for $i = m, m+1, .., (a_{k+1} - 1)/2$ , and we may no longer deduce the existence of an index $i$ for which $|S_i| = 0$ . The obvious computation now yields:

$|S| = |S_0| + \displaystyle \sum_{i=1}^{(a_{k+1} + 1)/2 - m} |S_i| \\ \le (m+1)/2 + (a_{k+1} + 1)/2 - m \\ = (a_{k+1} + 1)/2 - (m-1)/2 \\ = (n+2)/2$

And we’re done.

Posted in Uncategorized | Leave a Comment »

Removing Schanuel

May 14, 2012

Let $u_{a,b}$ and $v_{a,b}$ be coprime integers such that $v_{a,b}$ is positive and $\dfrac{u_{a,b}}{v_{a,b}} = \displaystyle \sum_{i=a}^b \dfrac{r_i}{i s_i}$ , where $\{r_i\}_{i \in \mathbb{N}}$ and latex $\{s_i\}_{i \in \mathbb{N}}$ are assumed to be given periodic sequences of integers. That is, for all $i$ we have $r_{i+t} = r_i$ for some $t \in \mathbb{N}$ and $s_{i+t'} = s_i$ for some $t' \in \mathbb{N}$ . In my paper I prove the following statement:

If Schanuel’s Conjecture holds, then for every $a \in \mathbb{N}$ , there exists an integer $b > a$ , such that $v_{a,b} < v_{a,b-1}$ . Furthermore, if $\max_i |s_i| = 1$ , then the smallest such $b$ grows at most linearly in $a$ .

I now believe I can prove the above, without assuming Schanuel’s Conjecture! Although I haven’t fully convinced myself that my ideas work, I’m getting more confident by the minute. I will now present an (admittedly very brief) overview of my ideas. I will expand on this as time goes on. Also, for definitions and lemma’s I refer to, check my preprint.

I use Schanuel’s Conjecture for two things:

1) To get an arbitrarily large prime $p$ dividing $X_b$ . (Theorem 2 in my preprint)
2) To make sure $\gcd(X_{a,b}, ls_b) < p$ .

It is, if I’m not mistaken, not hard to do the second part without Schanuel. We can prove that $l < p$ (as I do on page 14, beginning with ‘Now that we have shown that $X_n$ has arbitrarily large prime divisors’), and since $\gcd(X_{a,b}, ls_b) < p$ is immediate when $ls_b < p$ , we may assume $l > ps_b^{-1}$ . Since $p$ is arbitrarily large, $l$ is arbitrarily large too. In particular, it must be divisible by a large prime power. On the other hand, we can use Lemma 4, 5, or 6 to make sure that $X_{a,b}$ is not divisible by a large power of that prime, and we are done.

A proof of the first statement is somewhat more involved, but the idea is to take the following assumption:

There exists a finite set of primes, $\{p_1, p_2, .., p_m\}$ such that, for all $n$ , $|X_n|$ can be written as $|X_n| = p_1^{e_{1,n}} \cdots p_m^{e_{m,n}}$ .

And derive a contradiction by using nested intervals $I_1 \supset I_2 \supset .. \supset I_m$ such that for all $k \in \{1,2,..,m\}$ , there exists a $j \in \{1,2,..,m\}$ , such that $p_k^{e_{k,n}} < n$ for all $n \in I_j$ . In particular, $p_k^{e_{k,n}} < n$ for all $k$ and all $n \in I_m$ , which is, for large enough $n$ , a contradiction, since $|X_n| > n^m$ , by Lemma 3.

To do this, realize that the last sentence implies that, for all $n$ large enough, there exists an index $k = k(n)$ , such that $p_k^{e_{k,n}} > n$ . But if $c$ is an arbitrary constant, $n$ is large enough and $n'$ is the smallest integer larger than $n$ such that $p_{k(n)}^c$ divides $n'$ , then $p_{k(n)}^{e_{k(n),n'}} < n'$ . Now, if we take $c$ to be suitably large, then we have a large interval where $p_{k(n)}^{e_{k(n),n''}} < n''$ for all $n''$ inside this interval. Then, inside this interval, we repeat this trick with a different index $k'$ , and a slightly smaller constant $c$ , such that inside this interval, we find a slightly smaller interval, such that for all $n'''$ inside this smaller interval, we have $p_{k'}^{e_{k',n'''}} < n'''$ . Repeat this process $m$ times, and we have that $p_k^{e_{k,n''''}} < n''''$ for all $k$ and all $n''''$ in the last, smallest, interval (which, to be clear, is thus contained in all the others).

Hopefully the above made some sense. If not, just have a little patience and look forward to more elaboration, which will come in due time. In the mean time, try to embrace the glorious notation I laid out in this post.

EDIT (9 december 2012): Have a look here.

Posted in Uncategorized | Leave a Comment »

When subsets can be sumsets

April 27, 2012

Let $A$ and $B$ be sets of integers. With $A + B$ we denote the set of all integers that can be written as a sum of one term in $A$ and one term in $B$ . That is, $A + B = \{a + b | a \in A, b \in B\}$ . Let $n$ be any positive integer. If $S$ is any set of integers, we shall say that $S$ is n-summable, if sets $A$ and $B$ exist with $|A| = \infty$ , $|B| = n$ , and $A + B \subseteq S$ . Note that being 1-summable is equivalent to being infinite. We call $S$ n-large if there exists a non-negative integer $m = m(n)$ and infinitely many $k$ such that $|\{k, k+1, .., k + m\} \cap S| \ge n$ . Note that being 1-large is also equivalent to being infinite. And thus, $S$ is 1-summable if, and only if, $S$ is 1-large. In this post we will prove the following cute generalization of this fact:

A set $S$ is n-summable if, and only if, $S$ is n-large.

First we will prove that if $S$ is n-large, then $S$ is n-summable. To this end, let $k_1, k_2, ..$ be an infinite sequence such that for all $i \in \mathbb{N}$ , we have: $|\{k_i, k_i+1, .., k_i + m\} \cap S| \ge n$ . Define $S_i = (\{k_i, k_i+1, .., k_i + m\} \cap S) - k_i \subseteq \{0, 1, .., m\}$ . Then we have infinitely many $S_i$ , but at most $2^{m+1}$ distinct $S_i$ . And thus, there exists an infinite subsequence $i_1, i_2, ..$ with $S_{i_1} = S_{i_2} = ..$ . Now, define $A = \{k_{i_1}, k_{i_2}, .. \}$ and $B = S_{i_1}$ . Then, by construction, we have $A + B \subseteq S$ .

To prove the converse direction, assume $A$ is any infinite set of integers and assume $B = \{b_1, b_2, .., b_n\} \subseteq \mathbb{Z}$ , with $b_1 < b_2 < .. < b_n$ . Then we will prove that if $S$ is not n-large, then $A + B \not\subseteq S$ . So assume that $|\{k, k+1, .., k + m\} \cap S| \le n-1$ for all $k$ with $|k| > k_m$ . Now, let $a \in A$ be any integer larger (in absolute value) than $k_{b_n - b_1} + \max(|b_1|, |b_n|)$ . Then $a + B$ is a set of $n$ integers, all larger (in absolute value) than $k_{b_n - b_1}$ , with the difference between largest and smallest element being: $(a + b_n) - (a + b_1) = b_n - b_1$ . In particular, $a + B \not\subseteq S$ . And since $a + B \subseteq A + B$ , we also have $A + B \not\subseteq S$ .

Now, if we say $S$ is $\infty$ -summable if $A, B$ exist with $|A| = |B| = \infty$ and $A + B \subseteq S$ , then, unfortunately, it is not true that $S$ is $\infty$ -summable if $S$ is n-summable for all $n \in \mathbb{N}$ . A counterexample:

Define sets $S_1, S_2, ..$ as follows:

1) $|S_k| = l$ , where $l$ is the $k$ -th entry of https://oeis.org/A002260
2) If $|S_k| = l$ , then $S_k = \{10^k + l, 10^k + 2l, .., 10^k + l^2 \}$

Define $S = \bigcup_{k=1}^{\infty} S_k$ . Then $S$ is n-summable for all $n$ , because $S$ is n-large for all $n$ , with $m(n) = n(n-1)$ . Although it is also easy to construct explicit sets $A$ and $B$ with $|A| = \infty$ , $|B| = n$ , and $A + B \subseteq S$ . We claim, however, that $S$ is not $\infty$ -summable. If $S$ were $\infty$ -summable, then, by some appropriate addition or subtraction, we have $A + B \subseteq S$ for some infinite sets $A = \{a_1, a_2, .. \}$ and $B = \{b_1, b_2, .. \}$ , with $0 < a_1 < a_2 < ..$ and $0 = b_1 < b_2 < ..$ . In particular, $A \subseteq S$ . Now, if $a_j \in S_k \subseteq S$ with $|S_k| > b_2$ , then $a_j < a_j + b_2 < a_j + |S_k| < 10^{k+1}$ . And thus, $a_j + b_2$ either lies strictly between two elements of $S_{k}$ , or $a_j + b_2$ lies strictly between the largest element of $S_k$ and the smallest element of $S_{k+1}$ . Either way, $a_j + b_2 \notin S$ . So $A$ is contained in the sets $S_k$ that have no more than $b_2$ elements. Now, let $b_i$ be any element of $B$ larger than $(b_2)^2$ , and let $a_j \in S_k$ be any element of $A$ larger than $b_i$ . Then, since $|S_k| \le b_2$ , we have that $a_j + b_i > 10^k + (b_2)^2 \ge 10^k + |S_k|^2$ . And thus, $a_j + b_i$ is larger than the largest element of $S_k$ . On the other hand, $a_j + b_i \le 2a_j \le 2*(10^k + k^2) < 10^{k+1}$ , which is thus smaller than the smallest element of $S_{k+1}$ . And we must conclude that $a_j + b_i$ is not an element of $S$ ; contradiction.

I realize that the above proof that our counterexample works may be somewhat inelegant, so I might rewrite it soon. In which case I’ll probably explicitly prove something like the following: if $S$ is as above, $A$ is an infinite set, $B = \{b_1, b_2, .. \}$ with $0 = b_1 < b_2 < ..$ , and $A + B \subseteq S$ , then $|B| \le b_2$ .

At last, I have the following hunch, on which I’ll probably be working for the next few days/years:

If there exists an absolute constant $c$ , such that for all $n \in \mathbb{N}$ there exist infinitely many $k$ for which $|\{k, k+1, .., k + cn \} \cap S| \ge n$ , then $S$ is $\infty$ -summable.

Posted in Uncategorized | Leave a Comment »

On the non-monotonocity of the denominator of the sum of consecutive (generalized) unit fractions

April 12, 2012

I indeed merged the two articles mentioned in the two previous posts, into one glorious piece of awesome, if I may say so. I rewrote almost everything, gave new definitions, found better proofs, made more lemmas, etc. etc. I even changed the title. So now I’m waiting for some feedback from my thesis advisor, and then I can resubmit On the non-monotonicity of the denominator of generalized harmonic sums to Integers: The Electronic Journal of Combinatorial Number Theory 🙂

Edit: under heavy influence of MathOverflow (those guys are awesome), I wrote an introduction for my paper. The above version is updated.

Edit2: Although I didn’t get any feedback from my thesis advisor, I resubmitted! The waiting can begin.

Edit3 (05-12-2012): My paper got accepted!! The Referee Report was quite positive, actually. It asked me to change, out of 23 mathematically dense pages, exactly one letter. The above version is, probably, the final version.

Posted in Uncategorized | Leave a Comment »

On the non-monotonicity of the denominator of the sum of consecutive unit fractions

April 3, 2012

Within 24 hours I managed to solve a problem I posed in my first article (see previous post), and (!!) write the whole thing up. Maybe I’ll merge the two, or maybe this will be my second article: On the non-monotonicity of the denominator of the sum of consecutive unit fractions. Anyway, good day!

Posted in Uncategorized | Leave a Comment »

Sums of consecutive (generalized) unit fractions

March 10, 2012

Wow, I just submitted my very first article!! Big moment for me 😀 Let’s all hope Integers: The Elecronic Journal of Combinatorial Number Theory soon publishes Sums of consecutive (generalized) unit fractions. Woohooo! And, obviously, any feedback is greatly appreciated 🙂

Posted in Uncategorized | Leave a Comment »

A proof from the book

December 16, 2011

We shall prove the following identity:

$1 + 2 + 4 + 8 + .. + 2^{k-1} = 2^k - 1$ ,

with perhaps the most beautiful proof I have ever found.

Assume that we play a tournament with $2^k$ players, in which every game is a knock-out game between $2$ players. So in the first round there are $2^{k-1}$ games to be played, one for every $2$ people. Then in the second round only half of the players remains (i.e. $2^{k-1}$ ), so there are another $2^{k-2}$ games to be played, and so forth. Right up to the semi final and final, which are just $2^1$ and $2^0 = 1$ games, respectively. So the total amount of games played in the tournament is: $1 + 2 + 4 + 8 + .. + 2^{k-1}$ . Another way to see how many games total there are played is the following: in every game, exactly $1$ player gets eliminated. There is only one winner, so the other $2^k - 1$ players must get elimated somewhere. So the total amount of games played must equal $2^k - 1$ . Kablam.

Posted in Uncategorized | Leave a Comment »

Conjecture concerning sequences with a lot of consecutive elements with small lcm

December 7, 2011

Let $1 \le a_1 < a_2 < ..$ be an infinite sequence of positive integers, such that, if we define $A(n)$ to be the number of indices $i$ such that $\text{lcm}(a_i, a_{i+1})\le n$ , then we have for every $\epsilon > 0$ infinitely many $n$ such that $A(n) > (c - \epsilon)\sqrt{n}$ , where $c = \displaystyle \sum_{j=1}^{\infty} \dfrac{1}{(j+1)\sqrt{j}} \approx 1.86$ . In my previous post I claimed that such sequences exist, and in due time I will prove this claim, but for now, let’s assume it.

Now, let $\epsilon$ be small and $n_1 < n_2 < ..$ be the sequence of all $n$ such that $A(n) > (c - \epsilon)\sqrt{n}$ . Then I’d like to bluntly conjecture that there exist infinitely many $i$ such that $\dfrac{n_{i+1}}{n_i} > c_1\epsilon^{-4}$ , for some absolute $c_1$ . In particular, $\displaystyle \limsup \dfrac{n_{i+1}}{n_i}$ goes to $\infty$ as $\epsilon$ goes to $0$ , that is: $\displaystyle \lim_{\epsilon \rightarrow 0} \limsup_{i \rightarrow \infty} \dfrac{n_{i+1}}{n_i} = \infty$

Posted in Uncategorized | Leave a Comment »

Sequences with bounded lcm for consecutive elements

December 6, 2011

On page 83 of the pdf-file of Old and New Problems and Results in Combinatorial Number Theory, the following is asked: If we have an infinite sequence $1 \le a_1 < a_2 < ..$ of positive integers and set $A(n)$ to be the number of indices $i$ such that $\text{lcm}(a_i, a_{i+1}) \le n$ , do we then have $A(n) = O(\sqrt{n})$ ? In the following very short article I answer the finite version of this question, which also implies an affirmative answer to the original question: Sequences with bounded lcm for consecutive elements . I conjecture that the term $\log(2n)$ is superfluous, but to get rid of it completely, a more detailed approach is needed. By the way, the constant $c \approx 1.86$ is best possible, in the sense that it is possible to construct an infinite sequence such that, for every $\epsilon > 0$ and infinitely many $n$ , we have $A(n) > (c-\epsilon)\sqrt{n}$ .