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, 2011Erdö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, 2010Theorem.
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.