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?

## Archive for the ‘Problem Solving’ Category

### The Angel Problem

March 20, 2011### Erdösproblem 3, part III

November 4, 2010So far I found about 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:

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

If , then the can be split into subsets

, , .., such that for all with we have: , as long as .

This is known for (see here) and shows that 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 is still open, in any case

### Erdösproblem 3, part II

November 3, 2010I 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 and let be the least common multiple of all members of , for a set of positive integers. Then . Now, assume we have a partition of in two sets and with and . Then in particular we have:

And boom goes the dynamite.

### Solving a third Erdösproblem (?)

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

Is it true that if and then there exist or so that and ?

And I can’t find a way to do this where the ‘s are . And, if this indeed is a counterexample, I’m bold enough to conjecture that it’s the easiest. 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, 2010Assume is a set with , such that diverges. Let , each with probability . What can we say about when goes to infinity? Must there, for example, be infinitely many sign changes with probability ? It can’t be hard to show this for bounded , but what about for example? I honestly have no clue whatsoever.

EDIT 22 Februari 2011

I can show that there is a positive probability that for any , for large enough; Let be the smallest integer such that (note that this exists since the sum of is assumed to go to infinity).

Then either the probability that is at least or the probability that is at least (*). Assume the first case (second case goes analogous), then we have:

(*) It is fun to note that both are the case, independent of . This can be used to show that for all

### Generalizing generalities

October 31, 2010**Theorem.**

Let be the least common multiple of and with for all , for some and for some . Then for infinitely many .

*Proof.*

It is clear that it is necessary that the numerator of does not equal infinitely often. So let’s start with that. Assume that the numerator of *does* equal for some large , where is not a prime power. Then: . And since , we have , which is never a unit fraction. Let be an integer for which and be a prime larger than such that divides . Note that if such a prime doesn’t exist for any , we would have that all the prime divisors of (which, as we saw, exist for infinitely many ), are smaller than or equal to . But a prime divisor of which is smaller than or equal to also divides . And this would immediately imply our theorem. So we may assume the existence of a prime dividing . Now, let be any (positive) multiple of lcm and set ;

### Another generalization

October 31, 2010Let be the least common multiple of and , where for all and some . Then necessarily happens infinitely often.

*Proof.*

Assume a exists that divides for some . Note that we may assume so, because if such a doesn’t exist, we’re immediately done since every primedivisor of must then be smaller than or equal to and thus also be a divisor of . Let be any multiple of and . We then have:

### G-g-generalize

October 29, 2010I never meant for it to happen. It violates all intentions of this blog to generalize a theorem. So I’d like to blame Ernie Croot for the suggestion;

Let be any (unordered) set of integers. Let be the least common multiple of and , where for all . Then necessarily happens infinitely often in exactly cases: there either exists an odd prime for which for all , or all the are even. And it’s not even necessary to start the sum at .

### Another random conjecture

October 28, 2010In spirit of yesterdays post, could the following be true, wild as it is?;

implies

If true, can’t be far from the truth. Do we have ? I very much doubt it.. , and in any case.

EDIT: By just googling “harmonic number 16735” I found some articles from around 1990, that are devoted to exactly this conjecture and it seems like it’s true (it’s proven for all with the possible exception of , and ), but hard. The only remaining conjecture from the previous post seems to hold up too. Anyway, they use p-adic methods, which I am (still) not that familiar with, so I’m definitely going to search for some literature about it.

### Three random conjectures

October 28, 2010Please refute at least one of the following:

implies

implies

never happens

EDIT. , is quite a cute counterexample to the first of these.