Tag Archives: Discrepancy

Open Collaborative Mathematics over the Internet – Three Examples

After much hesitation, I decided to share with you the videos of my lecture: Open collaborative mathematics over the internet – three examples, that I gave last January in Doron Zeilberger’s seminar at Rutgers on experimental mathematics. Parts of the 47-minutes talk is  mathematical, while other parts are about mathematics on the Internet, blogs,  the polymath projects, MathOverflow, etc.

Here is the video of part I (30 minutes) and here is the video of  part II (17 minutes).

I tried to give some homage to Doron’s own lecture style, but when I saw the video, I could not ignore some aspects of my own style – complete indifference between plus and a minus, between x^2 and \sqrt x, between multiplying by something and dividing by the same thing, between subscripts and superscripts, between what are “rows: and what are “columns”, etc., and, in addition, randomly ending English words with an ‘s’ regardless of what English grammar dictates. Apologies. This was a rare occasion of giving a talk about “meta” matters of doing mathematics.

My first (and main) example was Erdős discrepancy’s problem, and I mentioned some experimental aspects, and heuristic arguments. The second example was Möbius randomness,  continued with some comments on MathOverflow, some  of the “goodies” one can earn participating in MathOverflow, and some comments on a debate regarding polymath projects organized by I.A.S a few years ago.  The third example was about mathematically oriented skepticism. This time not about my debate with Aram Harrow and quantum computing skepticism (that I briefly mentioned), but about my “Angry Birds” skepticism. The lecture was a mixture of a blackboard talk and presentation of various Internet site.

Summary and links

Here are the links to the Internet pages I presented with an outline of the lecture:

Video I (Erdős discrepancy problem)

00:00-00:43 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 polymath projects, mentioned polymath1 and density Hales-Jewett, other polymath projects, and polymath5.

4:00-12:00 Polymath5, discrepancy of hypergraphs, and The Erdős Discrepancy problem. [6:06 “There is nothing more satisfying in a lecture than seeing attempts by the speaker to move an unmovable blackboard”]; Some basic observations, random signs, Mobius functions, the log n example.

12:00-16:00 Plan for the next fifteen minutes: a) Greedy methods, b)Heuristic approaches, c) Hereditary discrepancy

17:00 – 18:40 Alex Nokolov and Kinal Talwar’s work on hereditary discrepancy. On the screen: Talwar’s post discrepancy to privacy and back on Windows on Theory

18:40 -23:00   Greedy approaches. On the screen:  My question on MathOverflow – on a certain greedy algorithm for Erdős discrepancy problem; The MO answer by ‘rlo’; a follow up question

23:00 – 27:00 What is MathOverflow. On the screen: my old MO page. (Here is the new one.) What is  “MO- reputation,” which “badges” you can earn and for what; Earning “hats” in more advanced site: On the screen:  hat champions from TCS-Stackexchange, winter 2012. (This webpage is no longer available.)

27:00 – 30:00 My heuristic approach for EDP

Video II (Möbius randomness, and angry birds)

On the screen: My MO question on Möbius randomness of the Walsh functions

00:00-02:00 Diversion: The IAS debate on polymath projects between Gowers and Sarnak, and comments  by me and by Noga Alon.

02:00-05:40  Möbius randomness and computational complexity. What is Mõbius randomness (MR);  Peter Sarnak’s Jerusalem talk on MR, his belief regarding the hardness of factoring, and my opinion; The AC^0 prime number conjectures and Walsh functions. My MO question; Ben Green’s MO-answer to one problem and Bourgain’s result answering a second question.

05:40-7:50 A remaining question on MR of Rudin-Shapiro sequences. On the screen – my MO question Mobius randomness of the Rudin-Shapiro sequence; What is a bounty in MathOverflow; Diversion: The power that comes with high reputation on MO. Who won my bounty.

7:50-09:30  My debate with Aram Harrow on my Quantum computers skepticism. On the screen the debates first post and then the post “can you hear the shape of a quantum computer?

09:30-14:30 Example 3: Another mathematically related skepticism – Angry Birds. On the screen this page from Arqade : Most voted questions (a few are very amusing); Introduction to the game “Angry Birds”; My skeptical theory: “Angry Birds” is becoming easier with new versions, and the statistical argument for it. I mentioned the Arqade’s question “Is angry Birds deterministic” that got (then) 143 upvotes, and was a role-model for me.

abd

14:30-17:00 My Arqade question, my hopes, and how it was accepted by the computer-games community;  On the screen: my Arqade question:

Continue reading

The Quantum Debate is Over! (and other Updates)

Quid est noster computationis mundus?

Nine months after is started, (much longer than expected,) and after eight posts on GLL, (much more than planned,)  and almost a thousand comments of overall good quality,   from quite a few participants, my scientific debate with Aram Harrow regarding quantum fault tolerance is essentially over. Some good food for thought, I hope. As always, there is more to be said on the matter itself, on the debate, and on other”meta” matters, but it is also useful to put it now in the background for a while, to continue to think about quantum fault tolerance in the slow pace and solitude, as I am used to, and also to move on in other fronts, which were perhaps neglected a little.

Here are the links to the eight posts: My initial post “Perpetual Motion of The 21st Century?” was followed by three posts by Aram. The first “Flying Machines of the 21st Century?” the second “Nature does not conspire” and the third “The Quantum super-PAC.” We had then two additional posts “Quantum refutations and reproofs” and “Can you hear the shape of a quantum computer?.” Finally we had  two conclusion posts: “Quantum repetition” and “Quantum supremacy or classical control?

EDP 22-27

We had six new posts on the Erdos Discrepancy Problem over Gowers’s blog (Here is the link to the last one EDP27). Tim contributed a large number of comments and it was interesting to follow his line of thought.  Other participants also contributed a few comments. One nice surprise for me was that the behavior of the hereditary discrepancy for homogeneous arithmetic progression in {1,2,…,n} was  found by Alexander Nikolov and  Kunal Talwar. See this post From discrepancy to privacy and back and the paper. Noga Alon and I showed that it is {\tilde{\Omega}(\sqrt{\log n})} and at most {n^{O(\frac{1}{\log\log n})}}, and to my surprise Alexander and Kunal showed that the upper bound is the correct behavior. The argument relies on connection with differential privacy.

Möbius randomness and computation

After the AC^0-prime number theorem was proved by Ben Green, and the Mobius randomness of all Walsh functions and monotone Boolean function was proved by Jean Bourgain, (See this MO question for details) the next logical step are low degree polynomials over Z/2Z . (The Walsh functions are degree 1 polynomials.) The simplest case offered to me by Bourgain is the case of the Rudin-Shapiro sequence. (But for an ACC(2) result via Razborov-Smolensky theorem we will need to go all the way to polynomial of degree polylog.) I asked it over MathOverflaw. After three months of no activity I offered a bounty of 300 of my own MO-reputations. Subsequently, Terry Tao and Ben Green discussed some avenues and eventually Tao solved the problem (and earned the 300 reputation points). Here is a very recent post on Möbius randomness on Terry Tao’s blog.

Influences on large sets

In my post Nati’s Influence I mentioned two old conjectures (Conjecture 1 dues to Benny Chor and Conjecture 2) about influence of large sets on Boolean functions. During Jeff Kahn’s visit to Israel we managed to disprove them both. The disproof is inspired by an old construction of Ajtai and Linial.

Tel Aviv, New Haven, Jerusalem

Last year we lived for a year in Tel Aviv which was a wonderful experience: especially walking on the beach every day and feeling the different atmosphere of the city. It is so different from my Jerusalem and still the people speak fluent Hebrew. I am now in New Haven. It is getting cold and the fall colors are getting beautiful. And it also feels at home after all these years. And next week I return to my difficult and beautiful  (and beloved) Jerusalem.

Alantha Newman and Alexandar Nikolov Disprove Beck’s 3-Permutations Conjecture

Alantha Newman and Alexandar Nikolov disproved a few months ago one of the most famous and frustrating open problem in discrepancy theory: Beck’s 3-permutations conjecture. Their paper  A counterexample to Beck’s conjecture on the discrepancy of three permutations is already on the arxive since April. (I was slow to get the news. Yuval Peres who heard it from Prasad Tetali told me about it today. You can read about it already on Joel Spencer’s homepage. Joel had offered 100$ prize for solving the conjecture that Alantha and Alexandar collected.)

The paper’s abstract tells the story.

Our previos post gives the basic definition of discrepancy of a hypergraph (=set-system), and describes a theorem by Beck and Fiala.

Abstract: Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. Jozsef Beck conjectured (c. 1987) that the discrepancy of this set system is O(1). We give a counterexample to this conjecture: for any positive integer n = 3^k, we exhibit three permutations whose corresponding set system has discrepancy \Omega (\log (n)). Our counterexample is based on a simple recursive construction, and our proof of the discrepancy lower bound is by induction. This example also disproves a generalization of Beck’s conjecture due to Spencer, Srinivasan and Tetali, who conjectured that a set system corresponding to l permutations has discrepancy O(\sqrt l).

Discrepancy, The Beck-Fiala Theorem, and the Answer to “Test Your Intuition (14)”

The Question

Suppose that you want to send a message so that it will reach all vertices of the discrete n-dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the message at round i all its neighbors will receive it at round i+1.

We will denote the vertices of the discrete n-cube by \pm 1 vectors of length n. The Hamming distance d(x,y) between two such vertices is the number of coordinates they differ and two vertices are neighbors if their Hamming distance equals 1. 

The question is

how many rounds it will take to transmit the message to all vertices?

Here is a very simple way to go about it: At round 1 you send the message to vertex (-1,-1,-1,…,-1). At round 2 you send the message to vertex (1,1,…,1). Then you sit and wait. With this strategy it will take \lceil n/2\rceil+1 rounds.

Test your intuition: Is there a better strategy?

The Answer: NO

The answer to the question posed in test you intuition (14) is no. There is no better strategy. The question was originated in Intel. It was posed by Joe Brandenburg and David Scott, and popularized by Vance Faber. The answer was proved by Noga Alon in the paper Transmitting in the n-dimensional cube, Discrete Applied Math. 37/38 (1992), 9-11. The result is closely related to combinatorial discrepancy theory and the proof is related to the argument in the Beck-Fiala theorem and a related lemma by Beck and Spencer. This is a good opportunity to present the Beck-Fiala Theorem.

The general form of a discrepancy problem

Let H be a hypergraph, i.e., a collection of subsets of a ground set A. A is also called the set of vertices of the hypergraphs and the subsets in H are also called edges.

The discrepancy of H, denoted by disc(H)  is the minimum over all functions f:A \to \{-1,1\} of the maximum over all  S \in H of

\sum \{f(s):s\in S\}.  

The Erdős Discrepancy Problem (EDP) asks about the following particular hypergraph: The vertices are {1,2,…,n} and the edges are sets of vertices which form arithmetic progressions of the form (r,2r,3r,…kr}. 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.

The Beck-Fiala theorem

Theorem (Beck-Fiala): If every element in A is included in at most t edges  of  H then disc(H)<2t.

Before proving this theorem we mention that it is a famous open conjecture to show that actually disc(H)=O(\sqrt t)

Proof:  Continue reading