The purpose of this post is to ignite some new activity related to polymath5 about Erdős’ Discrepancy Problem. This post is thus a polymath5 research thread and comments (also unrelated to the suggestions in this post) are welcome.
The general form of a discrepancy problem
Let be a hypergraph, i.e., a collection of subsets of a ground set
. The discrepancy of
, denoted by
is the minimum over all functions
of the maximum over all
of
.
We will mention one additional definition, that of hereditary discrepancy. When is a hypergraph and
, the restriction of
to
is the hypergraph with vertex set
whose edges are all sets of the form
for edges
of
. The hereditary discrepancy
of
is the maximum over all
of the discrepancy of
restricted to
.
Here is a link for a recent post discussing discrepancy and the famous Beck-Fiala theorem. The Beck-Fiala theorem assert that if every element in is included in at most
sets in
then
. (Of course, the theorem applies also to the hereditary discrepancy.)
The Erdős’ Discrepancy Problem reviewed
The problem and links to polymath5 material
Erdős Discrepancy Problem (EDP). Is it possible to find a -valued sequence
and a constant
such that
for every
and every
?
A HAP (Homogeneous Arithmetic Progression) is an arithmetic prograssion of the form {k,2k,…,rk}. EDP asks about the sum of a sequence on HAPs.
Given a sequence
define
to be the maximum of sums of subsequences over HAPs which are subsets of {1,2,3,…,n}. EDP asks if we can find a sequence for which
is uniformly bounded and we will be interested in finding sequences where
grows slowly.
EDP was extensively discussed and studied in polymath5. Here is the link of the first post. Here are links to all polymath5 posts. Here is the link to polymath5 wiki.
A sequence is called completely multiplicative if for every
and
. EDP is of great interest even if we restrict our attention to completely multiplicative sequences. For those we have only to consider partial sums
.
An example where the discrepancy grows like log n.
The function that takes n to 1 if the last non-zero digit of n in its ternary representation is 1 and -1 if the last non-zero digit is 2 is completely multiplicative and the partial sum up to n is easily shown to be at most . Therefore, the rate at which the worst discrepancy grows, as a function of the length of the homogeneous progression, can be as slow as logarithmic.
What a random assignment gives us.
A random sequence (or a random completely multiplicative sequence) gives us discrepancy close to . (There is apparently an additional
factor but I am not sure of the precise asymptotic behavior.)
Two greedy algorithms
From now on we write instead of
.
Greedy algorithm 1 (for multiplicative functions): Assign the value as to minimize the maximum discrepancy in every partial sum whose terms are now determined.
Greedy algorithm 1 (for general functions): Assign the value so as to minimize the maximum discrepancy in every HAP whose terms are now determined.
Problem 1: How does Greedy algorithm 1 perform?
Empirical observation: (This was claimed in some polymath 5 remarks but I am not sure if there was definite evidence. I would appreciate clarifications.) The discrepancy for sequences based on the greedy algorithm 1 (for multiplicative functions and for general functions) is .
Interpretation: Greedy algorithm 1 optimizes an “irrelevant task”.
We would like to suggest here
Greedy algorithm 2 (for multiplicative sequences): Assign the value so as to minimize the maximum discrepancy in every partial sum where unassigned entries get the value zero.
Greedy algorithm 2 (for general sequences ): Assign the value f(n) as to minimize the maximum discrepancy in every partial sum in every HAP where unassigned entries get the value zero.
Problem 2: How does Greedy algorithm 2 perform?
Omri Floman ran Greedy 2 on inputs such as N=10000 and got a discrepancy of around 20 (there is a bit of randomness involved in cases of ties). For N=100000 he got about 45. It is unclear what the behavior is.
Problem 3: Can we find an optimal compromise between Greedy 1 and Greedy 2?
Problem 4: Can randomization help?
Of course, since we know that a sequence of length n and discrepancy log n exists if we draw a random sequence there is a probability larger than
of reaching such a low discrepancy sequence. What we want to ask is if randomization can lead to a method of getting a low-discrepancy sequence with larger probability, or even better with provable larger probability. (Or even better yet, to a sequence of provable low discrepancy via an effective algorithm.)
Problem 5: How do Greedy algorithms 1 and 2 perform if we apply them for a random ordering of {1,2,…,n}.
Extensions of Erdős’ Discrepancy problems
Here are some variations of the Erdős’ Discrepancy Problem along with some guesses for the answers. I will explain where these guesses came from next time.
E0: Erdős’ Discrepancy Problem
Guess:
E1: Allow f(n) to attain values which are complex numbers of norm 1.
Guess, same answer
(Perhaps we can even consider norm-1 vectors in some Euclidean space or Banach space. If this is too premissive () we may go down to a constant.)
Square-free integers
E2: The EDP for square-free integers
Here we simply consider sequences where if
is not square-free. For this variation the multiplicative version of the problem is not a special case of the general question. (Here multiplicative means that
if
are coprime.)
Guess: for both versions, same answer
.
Random subsets of integers
E3: Instead of square-free integers consider a random dense subset of integers and assume that the sequence vanishes for indices not in the subset.
Guess: same answer .
Random sets of primes
Here we consider multiplicative functions which are non zero only on a random dense sert of primes.
E4: The EDP for a random dense subset of primes.
Guess: same answer
Problem 6: Find a sequence for problems E2, E3, and E4 with discrepancy , or better
or better
. Update: see below. It can be shown that sequences with discrepancy
exist for all these variations.
Prime power differences
E5: The EDP for HAP with prime power differences.
Guess:
.
Beurling primes and integers
Beurling primes were defined by Arne Beurling in 1937 and he also proved a prime number theorem for them. The most general definition is very simple: Consider a sequence of real numbers regarded as “primes” and consider the (ordered) sequence of their products (multiplicities allowed)
as the “integers”. (We will assume that all products are distinct although for the original purpose of defining a zeta function multiplicities may play a role.) Beurling primes played a role in the polymath4 discussions.
E6: The EDP for Beurling primes and integers
Careless Guess: at most
.
Sune Kristian Jakobsen’s systems of pseudointegers
One way to think about Beurling primes is to identify with
and to reorder the integers according to the ordering of the
s. Actually, given the ordering we can recover uniquely the Beurling primes. A much more general notion of “pseudointegers” was suggested over polymath5 by Sune Kristian Jakobsen. See also the overview over Polymath5’s wiki.
An ordering of the natural numbers is a SKJ-ordering if it fulfills the following two conditions:
1) If and
then
.
and
2) for any the set
is finite.
Remark: 1) Sune Kristian considered orderings on sequences of integers (the exponents in the prime factorization). This is equivalent to (but perhaps less provocative than) the formulation here. 2) We can expect that Beurling-orderings are a tiny tiny subset of SKJ-orderings.
Given an SKJ-ordering of the natural numbers we can ask the EDP for that ordering.
E7: The EDP for Sune Kristian Jakobsen systems of integers.
Careless Guess: at most polylog n
Problem 7: How does Greedy algorithm 2 perform for variations E2 -E7.
The answers for E2, E3 and E4 is especially interesting because these are examples where the best upper bounds I know behave like and are obtained from a random assignment. (See problem 5.)
Problem 8: Prove the assertion of EDP (namely that the discrepancy is unbounded) for an SKJ-pseudointegers of your choice.
Related Discrepancy Problems
Discrepancy and hereditary discrepancy
Recall that for a hypergraph defined on a ser
the discrepancy of
, denoted by
is the minimum over all functions
of the maximum over all
of
.
When is a hypergraph and
, the restriction of
to
is the hypergraph with vertex set
whose edges are all sets of the form
for edges
of
. The hereditary discrepancy
of
is the maximum over all
of the discrepancy of
restricted to
.
An operation of hypergraphs
Let be a hypergraph on a vertex set
and assume that
is ordered, e.g.,
. Consider the hypergraph
obtained from
by adding for every set
all its initial subsets w.r.t. the ordering. We will consider the operation of moving from
to
. Note that for EDP all our variations E1-E8 the underlying hypergraph is obtained by this construction
. (From a certain natural hypergraphs
). I further guess that for all the variations E1-E8 if we consider the hypergraph
(before taking initial segments) then the discrepancy is bounded.
Probabilistic versions
Let be a ground set and let
be a set of reals. First consider the discrepancy problem for a random hypergraph
with
edges, whose ith edge is a random set
so that every element of
belongs to
with probability
(and all these events are statistically independent). Next we can move from
to
as described above.
The case of taking for the probabilities
can be seen as a probabilistic analog of EDP. My guess for the discrepancy of this case is also
. I also guess that the discrepancy of
itself is bounded.
Problem 9: How do Greedy algorithms 1 and 2 perform for the random hypergraph .
Roth’s theorem about the discrepancy of arithmetic progressions
For EDP the ground set is all natural numbers, or just the set {1,2,…,n} and the hypergraph is the collection of all HAPs(homogeneous arithmetic progressions). Roth considered the hypergraphs of all arithmetic progressions. Roth proved that the discrepancy in this case is at . The existence of
with discrepancy of
was proved by Beck and the
factor was removed by Matousek and Spencer. These works by Beck, Matousek and Spencer may be very relevant to prove the existence of low-discrepancy sequences for EDP and some of its extensions.
Some results with Noga Alon
Here are some results proved in collaboration with Noga Alon which are based on the Beck-Fiala theorem and a general argument on moving from to
. (It is likely that some of them are known and we will be happy to know.)
Proposition 1: For the discrepancy of
described above is at most
.
This follows from the following general proposaition:
Proposition 2: Let be a hypergraph on an
element ordered set
and let
be the maximum degree of a point of
, then
.
Proof: Let be a partition of
into two nearly equal intervals,
a partition of
into 2 nearly equal intervals and similarly
, etc (
levels). Now define a new hypergraph
obtained from
by replacing each set
in
by the following
sets (possibly some empty):
,
,
,
![]()
(for all
),
.
Note that the maximum degree of a point in is
, hence the discrepancy of
is at most
by Beck-Fiala’s theorem. Also, each initial segment of
is a union of at most
pairwise disjoint members of
. This gives Proposition 1, and since for the case described in Proposition 2 the degree of vertices for
behaves like
we obtain Proposition 2 as well.
Proposition 3: for versions E1-E8 there are examples where the discrepancy is .
Proof: In all these examples we consider a hypergraph on the ground set A={1,2,…,n}, or on a subest of A with positive density (or for E7 and E8 on another non conventionally ordered set of integers). Then move to the hypergraph
of initial subsets of edges of
. To apply Proposition 2 and Beck-Fiala’s theorem we need to find an upper bound on the degree of a vertex in the hypergraph $\cal H$. Consider the case of EDP. (The other cases are similar.) The maximum degree is obtained by an integer that is the product of the first k distinct primes. In this case the degree
is smaller than
. Note that the proof applies even to hereditary discrepancy.
Problem 10: Use similar ideas to prove better (even polylog (n)) constructions for EDP and its variations E1–E8.
I extend all my earlier guesses when we move from discrepancy to hereditary discrepancy.
Proposition 4: The hereditary discrepancy for the hypergraph of HAP on {1,2,…,n} is .
The proof is obtained as follows: Consider the first primes, and a hypergraph
on {1,2,…,m} of discrepancy
. (For example, a Hadamard matrix of order
describes such an hypergraph. ) Next, for every edge
consider the integer that correspond to products of primes whose indices are in
. Then restrict your attention only to these integers.
Propositions 3 and 4 show that the hereditary discrepancy of the hypergraphs of HAPs in {1,2,…,n} is between and
.
A Quick Outlook at Polymath 5: EDP 1-21
Before our quick review of polymath5, let me mention a major difficulty which seems relevant to all approaches:
If we allow zero entries in our sequence, even a small density of zero entries, then the discrepancy can be bounded.
For example consider the sequence 1, -1, 0, 1, -1, 0, 1, -1, 0, …
Experimentations: Computer experiments played a large role in polymath5. One of the most striking discoveries was a sequence of length 1124 of discrepancy 2. Later a second sequence of length 1124 and discrepancy 2 was found but not a larger sequence. Several people made great contributions with computer experiments.
Additive Fourier analysis ideas: Using Fourier analysis on our sequence and somehow reaching a contradiction when we assume that the discrepancy is bounded was a suggestion that was dominant in the first few threads and we came back to from time to time.
Terry Tao’s reduction: Terry Tao found a reduction from the general question to the variation of multiplicative functions with complex norm-1 values (E1). The beautiful proof relies on “multiplicative” Fourier analysis and it is striking how “little” the proof uses.
Problem 11 (Sune Kristian Jakobsen): Does Tao’s reduction apply to arbitrary SKJ-pseudointegers.
Semi-definite programming: A major turning point was a suggestion by Moses Charikar to use a natural semi-definite relaxation for the problem. This promising avenue was explored over several threads and here too computer experimentation was done. One reason to regard Charikar’s approach (and the related linear programming approach described next) as hopeful is precisely because it offers a convincing way to get around the difficulty demonstrated by the sequence 1, -1, 0, 1, -1, 0, …
A generalization and linear programming: The last few threads were centered around a different related relaxation proposed by Tim Gowers. The problem was generalized from a single-sequence problem to a pair-of-sequences problem. (This is a common motif in extremal combinatorics although here the motivation came from functional analysis.) Then relaxation of the problem led to a very appealing linear programming question.
Mathoverflow questions: Mathoverflow was used to ask several questions related to the project.
Participation: Polymath 5 attracted much interest and wide participation. Overall, it did not attract researchers with major prior interest in discrepancy theory.
Discrepancy
Discrepancy theory is a huge an exciting area. Let me just give references to some books.
Jozsef Beck, William W. L. Chen: Irregularities of Distribution, Cambridge University Press, 1987. And, Jozsef Beck: Irregularities of Distribution (Cambridge Tracts in Mathematics Cambridge Tracts in Mathemat Volume 89)(Paperback)
Bernard Chazele: The Discrepancy Method: Randomness and Complexity
Jiri Matousek: Geometric Discrepancy: An Illustrated Guide (Algorithms and Combinatorics)
J. Beck: Combinatorial Games: Tic-Tac-Toe Theory, Cambridge University Press, 2008.
J. Beck: A forthcoming book.
Reading these books will prepare you better to deal with EDP and will enrich your life tremendously.
August 23, 2012 at 9:02 am |
[…] Erdos discrepancy problem (polymath5): Tim Gowers and I have a plan to try soon to revive the EDP project at least for a short while. We plan 3 posts about it in the second half of August over Tim’s blog. Update: The first post EDP22 just appeared. […]
August 23, 2012 at 10:59 am |
You have the formula
twice in the post. I think there should be absolute value signs around it in both cases.
Corrected now — Tim.
August 23, 2012 at 1:28 pm
Dear Sune, Right, my mistake. BTW did you explore further your notion of pseudointegers?
August 23, 2012 at 2:09 pm
Not anymore than what i have posted
August 24, 2012 at 11:42 am
Sune, I found your pseudointegers very interesting. I just remind the reasers that they can be regarded as total order relations on the positive integers, where a<b implies ac<bc and there are only finitely many integers smaller than any number n. For example you can ask: if the number of integers smaller than a prime p is roughly p
does this implies the statement of the prime number theorem? (Something of this kind is known for Beurling primes.) Two further questions: 1) I dont remember if you had examples for your pseudoprimes where EDP was violated? 2) Did you check if Tao's reduction works in this generality?
August 24, 2012 at 12:53 pm
1): Yes, here: https://gowers.wordpress.com/2010/02/08/edp7-emergency-post/#comment-6120 (as a reply to the comment you linked to. I couldn’t remember it before I read it).
We can also construct examples where the multiplicative EDP is true, by having arbitrarily long runs of consecutive squares.
2) No. I remember that I didn’t understood Tao’s proof, at least not well enough to check if it worked for the pseudointegers. I had hoped Tao could tell if it works!
September 1, 2012 at 9:08 am
“We can also construct examples where the multiplicative EDP is true, by having arbitrarily long runs of consecutive squares.” That does not hold: We can’t have two consecutive pseudointeger that are square in any set of pseudointegers. Assume for contradiction that x and y are consecutive and squares. We can write them as
and
. But then
, contradiction.
So I still haven't found a set of pseudointeger where I can prove EDP.
September 3, 2012 at 8:17 pm
Dear Sune, it somehow looks to me that your pseudo-integers are the same as Beurling’s integers. Maybe we can relax your definition and insist that c and d are relatively prime to a and b to get a more general notion.
September 4, 2012 at 9:02 am
Sune, if you can tell me what the statement following “such that” was supposed to be, then I will edit the comment. Tim
Dear GIl, yes it seems to be almost the same. Two Beurling’s integers are also allowed to correspond to the same real number, and that corresponds to the statement that we can have pseudo-integers a and b such that ab^{n}$ for all n. The only difference seems to be that pseudointegers have a complete ordering. The ordering of the Beurling’s integers come from a (possible not injective) map to the reals, so it might not be complete. But that is just a little extra structure so in the following I will use “Buerling’s integers” to mean what I used to call “pseudo integers”
I think that if you have a set of Beurling’s integers then for all n, the set of the first n of these Beurling’s integers will be isomorphic to a subset of
, and I think you lose this property if you generalise further.
August 23, 2012 at 11:46 am |
For
define
to be the smallest possible discrepancy of a sequence over
where the density of 0’s is at most p. We know that this is finite for all p>0: If
we can choose the sequence that is 0 on all multiples of
and sends
to
for all
. This should have discrepancy n.
EDP is equivalent to
. We could hope that the behavior of Z is simpler than that of E, since in the definition of E we are postponing problems, while in the definition of Z we are spreading them out.
August 23, 2012 at 2:15 pm
Could you elaborate on your last sentence: I find it intriguing but I don’t see exactly what you mean by it?
August 23, 2012 at 3:23 pm
First,
in the above should have been
(I hope).
It seems that I was a bit too sloppy both when I read the definition of E and when I posted the above comment. I though the definition of E(n) was “the smallest possible discrepancy of a sequence of length n”.
What I meant was: One way to investigate EDP is to fix some integer d and try to find the longest possible sequence with discrepancy below d. The sequences we get are then optimized to keep the discrepancy at most d for as long as possible, and it might be that for all extensions of the sequence the discrepancy grows to, say, 3/2d, within the next few terms. This is what I mean by “postponing the problems”.
Instead we might try to keep the discrepancy below d while defining the sequence on a subset of
with positive density (and setting all other terms to 0). If the positions of these 0’s are periodic, as in the low-discrepancy examples we know, then it will be possible to fill out more terms without increasing the discrepancy by much.
August 23, 2012 at 3:44 pm
The downside of this approach is that the definition of Z involves infinite sequences. It is not even clear if there is a way to compute Z(p) for a given p.
August 24, 2012 at 6:52 am
You could combine the two ideas, by considering
, the minimal HAP-discrepancy over sequences
where
for at most
values of
in the range
(and there’s no restriction for values greater than
).
Then your
is just
, and
.
It could be interesting to think specifically about where the zero values should be placed in order to minimize the discrepancy in this context.
August 26, 2012 at 1:35 am |
Very interesting post!
Some notes on the operation on hypergraphs. The short version of this comment is that Prop 2 can be tightened, and also generalized to show that the operation on hypergraphs increases hereditary discrepancy by at most a polylog factor.
1) Prop 2 holds with the bound
latex H$ is
). This follows from the following theorem by Banaszczyk:
> For any convex set
of gaussian measure at least 1/2 and any set of vectors
each of euclidean norm at most 1/10, one can find a
such that
.
Let
be the incidence matrix of
(as you define it in your proof). Scale down the columns of
by
for a large enough constant
so that each column has norm at most 1/10 and let the scaled columns be
.
Let
be the incidence matrix of
and
be such that
. As you argue, each row of
can be taken to be a 0-1 vector with at most
1’s, so each row of
can be taken to have euclidean norm
. Define
. Clearly
is convex and for large enough
has gaussian measure at least 1/2. By Banaszczyk’s theorem, we can find
such that
, and scaling
back up we have found
such that
.
2) If
is the result of applying the transformation on
and
has
sets,
.
The proof is similar to yours. Take
be the result of replacing each set
with
and
;
: the result of replacing
with
for all
and so forth. This gives us
for
. Since each
is the union of *disjoint* restrictions of
, for all
we have
. Then
and by a recent result of Matousek,
. Finally, as you argue,
.
August 26, 2012 at 1:39 am |
Sorry, the above didn’t parse right, I am not very good with this wordpress-latex thing..
Some notes on the operation on hypergraphs. The short version of this comment is that Prop 2 can be tightened, and also generalized to show that the operation on hypergraphs increases hereditary discrepancy by at most a polylog factor.
1) Prop 2 holds with the bound
(assuming the number of sets of
is
). This follows from the following theorem by Banaszczyk:
For any convex set
of gaussian measure at least 1/2 and any set of vectors
each of euclidean norm at most 1/10, one can find a
such that
.
Let
be the incidence matrix of
(as you define it in your proof). Scale down the columns of
by
for a large enough constant
so that each column has norm at most 1/10 and let the scaled columns be
.
Let
be the incidence matrix of
and
be such that
. As you argue, each row of
can be taken to be a 0-1 vector with at most
1’s, so each row of
can be taken to have euclidean norm
. Define
. Clearly
is convex and for large enough
has gaussian measure at least 1/2. By Banaszczyk’s theorem, we can find
such that
, and scaling
back up we have found
such that
.
2) If
is the result of applying the transformation on
and
has
sets,
.
The proof is similar to yours. Take
be the result of replacing each set
with
and
;
: the result of replacing
with
for all
and so forth. This gives us
for
. Since each
is the union of *disjoint* restrictions of
, for all
we have
. Then
and by a recent result of Matousek,
. Finally, as you argue,
.
August 26, 2012 at 2:14 pm
Dear Sasho, This is very interesting!
August 26, 2012 at 8:43 am |
Some information regarding greedy algorithm 2 can be found in
Robert Lemke Oliver’s answer to this MathOverflow question
http://mathoverflow.net/questions/105383/the-behavior-of-a-certain-greedy-algorithm-for-erds-discrepancy-problem
August 26, 2012 at 9:30 am |
Terry Tao’s reduction of the problem to one about multiplicative sequences (described here) also invites a class of negative attacks that may conceivably be easier than the direct search for a counterexample. Namely, can one find a method of generating a random multiplicative sequence
such that (with respect to the resulting random distributiom) the expectation of
is bounded as a function of
? Such a method would (as shown at the bottom of that wiki page) imply a counterexample to the Hilbert-space version of EDP.
August 26, 2012 at 9:59 pm |
[…] Autumn I prepared three posts on the problems and we decided to launch them now. The first post is here. Here is a related MathOverflow question. Discrepancy theory is a wonderful theory and while I am […]
August 27, 2012 at 6:26 pm |
Perhaps it is worth adding also
Proposition 5: For every
there is a set of the natural numbers of density
such that restricted to this set the discrepancy of HAPs in {1,2,…,n} is at most polylog (n).
prime factors for sifficiently large
, and apply Proposition 2
Proof: Simply consider natural numbers with at most
.
August 29, 2012 at 4:52 pm
I meant the hereditary discrepancy. (for discrepancy there are esaier things that can be done..)
September 4, 2012 at 7:15 pm |
Last week Kunal Talwar and I thought a bit about the hereditary discrepancy of HAPs. We can show that the hereditary discrepancy is not polylogarithmic; in fact it is
, which, as the upper bound in Gil’s post shows is tight up to the constant in the exponent.
Below I am writing a sketch of how the proof goes. Since the proof itself got a bit long, we wrote a note: you can find it here.
(1) Consider the following set system of boolean subcubes, let’s call it
. Each element of the ground set is identified with a boolean vector
. We get each set from fixing some of the coordinates and leaving the other ones free. That is, each set
is associated with a vector
and consists of those
for which
whenever
.
(2) We construct a set of positive integers
by associating an integer to each boolean vector
so that each
corresponds to a HAP restricted to
. This is not hard and is similar to the construction in the post. We pick the first
primes
and associate
to each
. The set
corresponds to the HAP with difference
.
(3) We show that
This proceeds in two steps:
3.1 Use the determinant lower bound of Lovasz, Spencer, and Vesztergombi to show that the matrix of Fourier characters of
of weight
(
a constant) has hereditary discrepancy
. Call this matrix 
3.2. Show that
. This goes by writing a character of weight
as a linear combination of
indicator vectors of subcubes. This is possible since a character of weight
is a function of
components.
We can choose
so that 3.1 and 3.2 imply (3).
September 13, 2012 at 3:35 am
By request from Gil: you can read another perspective on the results above in a blog post Kunal posted on an MS Research computer science theory blog: http://windowsontheory.org/2012/09/05/from-discrepancy-to-privacy-and-back/. The post focuses on connections with computer science (specifically differential privacy) that gave us some intuition.
September 13, 2012 at 7:03 pm
Very nice result. It is nice to see the hereditary discrepancy of HAP being completely understood and also the relation with privacy is very nice.
September 5, 2012 at 4:33 pm |
[…] the EDP, it is natural to ask how large the hereditary discrepancy is. Alon and Kalai show that it is and at most . They also showed that for constant , it is possible to delete an […]
October 15, 2012 at 4:56 am |
[…] Kunal Talwar. See this post From discrepancy to privacy and back and the paper. Noga Alon and I showed that it is and at most , and to my surprise Alexander and Kunal showed that the upper bound is […]
November 17, 2012 at 5:35 pm |
[…] and Talwar of the hereditary discrepancy analog for Erdos’ discrepancy problem. See also this post in Gowers’s […]
August 19, 2013 at 2:06 pm |
[…] Doron’s introduction; 00:43-4:00 On the screen: Erdős discrepancy problems: showing this post (EDP22) from Gowers’s blog. I talked about the chaotic nature of mathematics on the Internet. Then I explained what are […]
February 28, 2014 at 4:10 pm |
[…] in Logic and Computation. They have recently made important progress on the Erdős Discrepancy Problem using computer tools from logic. Unlike the approach of a PolyMath project on the problem, their […]