Conference rusure::math

1646.0. "problems from net, sorry if allready posted" by STAR::ABBASI (i^(-i) = SQRT(exp(PI))) Fri Jul 24 1992 18:02

Article: 29988
Xref: nntpd.lkg.dec.com rec.puzzles:17055 sci.math:29988
Path: nntpd.lkg.dec.com!news.crl.dec.com!deccrl!caen!zaphod.mps.ohio-state.edu!think.com!ames!agate!manifold.berkeley.edu!greg
From: [email protected] (Greg Kuperberg)
Newsgroups: rec.puzzles,sci.math
Subject: The Erdos kitty:  At least $9050 in prizes!
Date: 11 Jul 1992 01:15:17 GMT
Organization: U.C. Berkeley
Lines: 120
Distribution: world
Message-ID: <[email protected]>
NNTP-Posting-Host: manifold.berkeley.edu
 
Paul Erdos, the Hungarian problem solver extraordinaire, has offered
money for so many problems that I have decided to separate them from
the rest of my list.  This posting is a partial list of Erdos prize
problems.  At least $9050, and perhaps as much as $34100, in prizes,
are here for the taking!
 
Many of these problems were formulated jointly by Erdos and other
mathematicians.  However, Erdos is the purser of all of the problems.
As I have mentioned before, the purser is the final judge and arbiter
of prize-winning solutions to each of the problems.  The
award for a problem only goes to the person who solves it first,
and the purser is the arbiter of that too.  I have given
my own description of each problem, but I am not responsible
for the consequences of mistakes or misleading wording in my
formulation.
 
If you are getting somewhere one of the problems, or if you plan
to try, you can contact me at [email protected].  Please
contact me if you know of other Erdos prize porblems.
 
The problems listed here are from two sources:
 
T = A Tribute to Paul Erdos, Cambridge University Press, 1990, pp. 467-477.
P = Paths, Flows, and VLSI Layout, Springer-Verlag, 1980, pp. 35-45
 
The problems are labeled by their source and number in the reference.
In addition, problems in the first reference are labeled by topic:
 
N = Number theory
C = Combinatorics and graph theory
G = Geometry
 
----------------------------------------------------------------------------
 
$10000. (T4N) Consecutive primes are often far apart
Conjecture:  For every real number C, the difference between the n'th
prime and n+1'st prime exceeds
 
C log(n)log(log(n))log(log(log(log(n))))/log(log(log(n)))^2
 
infinitely often.  (The wording in the source does not clearly indicate
that the money will be awarded if the conjecture is disproved, only if
it is proved.)
 
 $3000. (T3N) Divergence implies arithmetic progressions
If the sum of the reciprocals of a set of positive integers is
infinite, must the set contain arbitrarily long finite arithmetic
progressions?
 
 $1000. (T2N) Unavoidable sets of congruences
A set of congruences n = a_1 mod b_1, n = a_2 mod b_2,... is
unavoidable if each n satisfies at least one of them.  Is there an N such
that every unavoidable set of congruences either has two equal moduli
b_i and b_j or some modulus b_i less than N?
 
 $1000. (T1C) Three-petal sunflowers
Is there an integer C such that among C^n sets with n elements, there
are always three whose mutual intersection is the same as each pairwise
intersection? (Problem P2 is the same, except that Erdos asks about
k-petal sunflowers for every k but then says he would be satisfied with
k=3.)
 
  $500. (T7N) Asymptotic bases of order 2 (I)
Consider an infinite set of positive integers such that every
sufficiently large integer is the sum of two members of the set.  Can
there be an N such that no positive integer is the sum of two members
of the set in more than N ways?
 
  $500. (T8N) Asymptotic bases of order 2 (II)
In the context of the previous problem, let f(n) be the
number of ways that n is the sum of two members of the set.
Can f(n)/log(n) converge to a finite number as n goes to infinity?
 
  $500. (T9N) Evenly distributed two-colorings
Given a black-white coloring of the positive integers, let A(n,k) be
the number of blacks minus the number of whites among the first n
multiples of k.  Can the range of A be bounded on both sides?
 
  $500. (T4C) Friendly collections of half-sized subsets
Given 1+((4n choose 2n) - (2n choose n)^2)/2 distinct, half-sized
subsets of a set with 4n elements, must there be two subsets which
intersect only in one element?  (As problem P1, 250 pounds is offered.)
 
  $500. (T1G) Uniformity of distance in the plane (I)
Is there a real number c such that n points in the plane always
determine at least cn/sqrt(log(n)) distinct distances?
 
  $500. (T1G) Uniformity of distance in the plane (II)
Is there a real number c such that given n points in the plane, no more
than n^(1+c/log(log(n))) pairs can be unit distance apart?
 
  $500.  (P2) Sets with distinct subset sums 
Is there a real number c such that, given a set of n positive integers
whose subsets all have distinct sums, the largest element is at least
c2^k?  (As problem T1N, no prize is mentioned.)
 
  $250.  (P4) Collections of sets not represented by smaller sets
Is there a real number c such that for infinitely many positive
integers n, there exists cn or fewer sets with n elements, no two of
which are disjoint, and every n-1-element set is disjoint from at least
one of them?
 
  $250/$100. (P15) Slowly increasing Turan numbers
If H is a (simple) graph, the Turan number T(n,H) is the largest number
of edges a graph with n vertices can have without containing a copy of
H.  Conjecture:  the function f(n) = T(n,H)/n^(3/2) is bounded above if
and only if every connected subgraph of H has a vertex of valence 1 or
2.  The larger award would be granted for a proof.
 
  $100/$25000.  (T6N) Consecutive early primes
An early prime is one which is less than the arithmetic mean of the
prime before and the prime after.  Conjecture:  There are infinitely
many consecutive pairs of early primes.  The larger award would be
granted for a disproof.
 
  $100. (T8G) Quadrisecants in the plane
Given an infinite sequence of points in the plane, no five of which are
collinear, let r(n) be the number of lines that pass through four
points among the first n.  Can it happen that r(n)/n^2 does not
converge to zero?