The Angel Problem

March 20, 2011

Go to http://library.msri.org/books/Book29/files/conway.pdf. Read the proof of Theorem 3.1. Am I being ridiculous if I believe it to be incorrect?

I’m done.

February 1, 2011

From its start back in May 2010, this blog has been one big failure. It took me over half a year, but I finally realised that I

– Can’t write
– Can’t present math in a clear fashion
– Can’t be bothered to write posts on a regular basis

At least these things are all true when the language I use is English. So, if Chewbacca lives on Endor, I must quit!

Probably, this implies that I will start a new blog sometime in the future. That could be in a few months, but it could also be in a few decades, I dont know. When the time is ripe, I will let you know. That’s a promise. You might ask why I would want to start a new blog, ever, given the above three reasons why this one failed. Well, because I can say that I learned a lot from this blog, so I can confidentially assert that my writing will be better next time.

Catch you on the flipside.

Random update

November 23, 2010

The reason for the fact that is has been more than 2 weeks since my last update is simple; contrary to popular belief, I have been busy. With a few things actually. I have been a bit busy studying (who would’ve thought). I have been busy writing my first article (thank you very much), which will be finished end of the week, hopefully. I have been busy playing guitar (obviously, I suck). And, last but not least, I have been juggling like there was no tomorrow (again, I suck). When I’ll improve, I might put some videos of me juggling here. That ought to be fun 🙂 My personal bests are, as of this moment:

3 balls: 12 minutes (close to 2500 catches)
4 balls: 57 seconds (over 200 catches)
5 balls: 15 catches
6 balls: 6 catches
7+ balls: err, no

I’ll update you on all of these things as soon as I’ve got some news.

EDIT 25 november: Woohoo! I flashed 6 balls 😀
EDIT 30 november: I updated a few personal bests. As of tomorrow I won’t do that anymore to be able to track my progress. But right now I’m too happy with my clean run of 15 😀

November 5, 2010

A variant on a well-known poem;

The title (basically) said it and I again will say
I’m in my prime; today it’s my 21st birthday!

Erdösproblem 3, part III

November 4, 2010

So far I found about $10$ more, what I like to call, NP-primitive counterexamples to the question asked here. When do I call a counterexample NP-primitive? When it’s easy to show (by the reasoning from the previous post) that it’s indeed a counterexample and if no (strict) subset of it is a NP-primitive counterexample. And given a NP-primitive counterexample, it’s easy to construct other easy to check counterexamples. The question now is of course: are there infinitely many NP-primitive counterexamples? Conceivably, this is not too hard. The ones I found so far:

$\{2,3,4,5,6,8,9,10,12,15,16\}$
$\{2,3,4,5,6,7,8,9,15,16,24\}$
$\{2,3,4,5,6,7,8,9,10,15,230\}$
$\{2,3,4,5,6,8,9,10,12,15,18,180\}$
$\{2,3,4,5,6,7,8,9,14,15,31,2474\}$
$\{2,3,4,5,6,7,8,9,11,15,75,8153\}$
$\{2,3,4,5,6,7,8,9,12,13,93,44155\}$
$\{2,3,4,5,6,7,8,10,12,14,60,105\}$
$\{2,3,4,5,6,7,8,10,12,15,42,210,420\}$
$\{3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,21,72,453\}$
$\{3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,30,154,315\}$
$\{3,4,5,6,7,8,9,10,11,12,13,14,15,18,20,24,30,840,450450\}$

And you can even make more by e.g. replacing $60$ in the fifth to last set with $120$, $140$ and $840$. A more general, and to me more sensible, conjecture of Erdös, Graham and Spencer is the following:

If $\displaystyle \sum_{i=1}^k \dfrac{1}{x_i} < N - \dfrac{1}{m}$, then the $x_i$ can be split into $N$ subsets
$A_1$, $A_2$, .., $A_n$ such that for all $j$ with $1 \le j \le N$ we have: $\displaystyle \sum_{a_i \in A_j} \dfrac{1}{a_i} \le 1$, as long as $m$ $\le 30$.

This is known for $m = \dfrac{7}{2}$ (see here) and $\{2,3,3,5,5,5,5\}$ shows that $m = 30$ is tight. Very probably this conjecture is cute enough to deserve a closer look at sometime.

EDIT: A counterexample to this last conjecture was found by Song Guo (Electronic J. of Combinatorics 15 (2008), #N43). You can find it online, if you’re interested. That paper also refers to other articles about these conjectures. The main question of finding the maximal $m$ is still open, in any case

Erdösproblem 3, part II

November 3, 2010

I checked my dictionary, but apparently there is no english word for the dutch word ‘tangconstructie’. Anyway, remember how I, rhetorically, asked ‘how else could it be?’ yesterday? Well, I am more than delighted to say that I am able to give a counterexample to the metaconjecture that every proof of a counterexample to the question of Erdös and Graham I talked about in the previous post, works via a case-by-case-argument.

Consider the set $X = \{2,3,4,5,6,8,9,10,12,15,16\}$ and let $lcm\{S\}$ be the least common multiple of all members of $S$, for a set $S$ of positive integers. Then $\displaystyle \sum_{x_i \in X} \dfrac{1}{x_i} = 2 - \dfrac{1}{lcm\{X\}}$. Now, assume we have a partition of $X$ in two sets $A$ and $B$ with $\displaystyle \sum_{a_i \in A} \dfrac{1}{a_i} < 1$ and $\displaystyle \sum_{b_i \in B} \dfrac{1}{b_i} < 1$. Then in particular we have:

$2 - \dfrac{1}{lcm\{X\}}$
$= \displaystyle \sum_{x_i \in X} \dfrac{1}{x_i}$
$= \displaystyle \sum_{a_i \in A} \dfrac{1}{a_i}$ $+$ $\displaystyle \sum_{b_i \in B} \dfrac{1}{b_i}$
$\le 1 - \dfrac{1}{lcm\{A\}} + 1 - \dfrac{1}{lcm\{B\}}$
$\le 2 - \dfrac{2}{lcm\{X\}}$

And boom goes the dynamite.

Solving a third Erdösproblem (?)

November 2, 2010

In their monograph on problems in combinatorial number theory, Erdös and Graham ask the following question:

Is it true that if $1 < x_1 < x_2 < .. < x_k$ and $\displaystyle \sum_{i=1}^k \dfrac{1}{x_i} < 2$ then there exist $\epsilon_i = 0$ or $1$ so that $\displaystyle \sum_{i=1}^k \dfrac{\epsilon_i}{x_i} < 1$ and $\displaystyle \sum_{i=1}^k \dfrac{1-\epsilon_i}{x_i} < 1$?

And I can’t find a way to do this where the $x_i$‘s are $\{2,3,4,5,6,8,9,11,12,13,16\}$. And, if this indeed is a counterexample, I’m bold enough to conjecture that it’s the easiest. $\{2,3,4,5,6,7,8,11,12,13,33\}$ could very well be a candidate too, but I haven’t checked that one thoroughly.

Edit: I now proved that the first one of these is indeed a counterexample, but of course, the proof is a case-by-case-argument (how else could it be?), so I won’t put it here, because of uglyness.

Weighed cointossing

November 2, 2010

Assume $S = \{s_1, s_2, .. \}$ is a set with $1 \le$ $s_1$ $\le s_2 \le ..$, such that $\displaystyle \sum \dfrac{1}{s_i}$ diverges.  Let $a_i = \pm 1$, each with probability $\dfrac{1}{2}$. What can we say about $\displaystyle \sum_{i=1}^n \dfrac{a_i}{s_i}$ when $n$ goes to infinity? Must there, for example, be infinitely many sign changes with probability $1$? It can’t be hard to show this for bounded $s_i$, but what about $S = \aleph$ for example? I honestly have no clue whatsoever.

EDIT 22 Februari 2011
I can show that there is a positive probability that $\left|\displaystyle \sum_{i=1}^n \dfrac{a_i}{s_i}\right| > c$ for any $c$, for $n$ large enough; Let $k = k(c)$ be the smallest integer such that $\displaystyle \sum_{i=1}^k \dfrac{1}{s_i} > c$ (note that this $k$ exists since the sum of $\dfrac{1}{s_i}$ is assumed to go to infinity).
Then either the probability that $\displaystyle \sum_{i=k+1}^n \dfrac{a_i}{s_i}$ $\ge 0$ is at least $\dfrac{1}{2}$ or the probability that $\displaystyle \sum_{i=k+1}^n \dfrac{a_i}{s_i}$ $\le 0$ is at least $\dfrac{1}{2}$ (*). Assume the first case (second case goes analogous), then we have: $P\left(\displaystyle \sum_{i=1}^n \dfrac{a_i}{s_i} > c\right) \ge P\left(\displaystyle \sum_{i=k+1}^n \dfrac{a_i}{s_i} \ge 0\right) \displaystyle \prod_{j=1}^k P(a_j = 1) \ge \dfrac{1}{2}\dfrac{1}{2^k} = \dfrac{1}{2^{k+1}} > 0$

(*) It is fun to note that both are the case, independent of $S$. This can be used to show that $P\left(\left|\displaystyle \sum_{i=1}^n \dfrac{a_i}{s_i}\right| > c\right) \ge \dfrac{1}{2^k}$ for all $n$ $\ge$ $k$

Generalizing generalities

October 31, 2010

Theorem.
Let $L_n$ be the least common multiple of $\{1,2,..,n\}$ and $X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{r_i}{i s_i}$ with $r_i, s_i \in Z$ for all $i$, $r_{i+m} = r_i$ for some $m$ and $s_{i+m'} = s_i$ for some $m'$. Then $\gcd(X_n, L_n) > 1$ for infinitely many $n$.

Proof.
It is clear that it is necessary that the numerator of $X_n$ does not equal $1$ infinitely often. So let’s start with that. Assume that the numerator of $X_{n-1}$ does equal $1$ for some large $n$, where $n$ is not a prime power. Then: $|X_n| + |X_{n-1}| \ge |X_n - X_{n-1}| = \left|\dfrac{L_n r_n}{n s_n}\right| > \dfrac{L_n}{n^2} > 2$. And since $|X_{n-1}| \le 1$, we have $|X_n| > 1$, which is never a unit fraction. Let $a$ be an integer for which $a \ge \max(m, m', \displaystyle \max_i (|s_i|))$ and $p$ be a prime larger than $a$ such that $p$ divides $X_a$. Note that if such a prime doesn’t exist for any $a$, we would have that all the prime divisors of $X_a$ (which, as we saw, exist for infinitely many $a$), are smaller than or equal to $a$. But a prime divisor of $X_a$ which is smaller than or equal to $a$ also divides $L_a$. And this would immediately imply our theorem. So we may assume the existence of a prime $p$ $> a \ge$ $\max(m, m', \displaystyle \max_i(|s_i|))$ dividing $X_a$. Now, let $k$ be any (positive) multiple of lcm$(\varphi(m), \varphi(m'))$ and set $n = ap^k$;

$X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{r_i}{i s_i}$
$\equiv L_n \displaystyle \sum_{i=1}^a \dfrac{r_{ip^k}}{ip^k s_{ip^k}}$ $\pmod{p}$
$\equiv \dfrac{L_n}{p^k} \displaystyle \sum_{i=1}^a \dfrac{r_i}{i s_i}$      $\pmod{p}$
$\equiv 0$                      $\pmod{p}$

Another generalization

October 31, 2010

Let $L_n$ be the least common multiple of $\{1,2,..,n\}$ and $X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{b_i}{i}$, where $b_{i+m}$ $= b_i \in \aleph$ for all $i$ and some $m$. Then $\gcd(X_n, L_n) > 1$ necessarily happens infinitely often.

Proof.
Assume a $p > a$ exists that divides $X_a = L_a \displaystyle \sum_{i=1}^a \dfrac{b_i}{i}$ for some $a \ge m$. Note that we may assume so, because if such a $p$ doesn’t exist, we’re immediately done since every primedivisor of $X_a$ must then be smaller than or equal to $a$ and thus also be a divisor of $L_a$. Let $k$ be any multiple of $\varphi(m)$ and $n = ap^k$. We then have:

$X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{b_i}{i} \equiv L_n \displaystyle \sum_{i=1}^a \dfrac{b_{ip^k}}{ip^k} \equiv \dfrac{L_n}{p^k} \displaystyle \sum_{i=1}^a \dfrac{b_i}{i} \equiv 0 \pmod{p}$