Game Theory – on-line Course at IDC, Herzliya

Game theory, a graduate course at IDC, Herzliya; Lecturer: Gil Kalai; TA: Einat Wigderson,  ZOOM mentor: Ethan.

Starting Tuesday March 31, I am giving an on-line course (in Hebrew) on Game theory at IDC, Herzliya (IDC English site; IDC Chinese site). There will be a page here on the blog devoted to this course.

In addition to the IDC moodle (course site) that allows IDC students to listen to recorded lectures, submit solutions to problem sets , etc., there will be a page here on the blog devoted to the course.

A small memory: In 1970 there was a strike in Israelis’ high schools and I took a few classes at the university. One of these classes was Game theory and it was taught by Michael Maschler. (I also took that trimester a course on art taught by Ziva Meisels.) Our department at HUJI is very strong in game theory, but once all the “professional” game theorists retired, I gave twice a game theory course which I enjoyed a lot and it was well accepted by students. In term of the number of registered students, it seems that this year’s course at IDC is quite popular and I hope it will be successful.

The first six slides of the first presentation

(Click to enlarge)

Game Theory 2020, games, decisions, competition, strategies, mechanisms, cooperation

The course deals with basic notions, central mathematical results, and important examples in non-cooperative game theory and in cooperative game theory, and with connections of game theory with computer science, economics and other areas.

What we will learn

1. Full information zero-sum games. The value of a game. Combinatorial games.

2. Zero-sum games with incomplete information. Mixed strategies, the Minmax Theorem and the value of the game.

3. Non cooperative games, the prisoner dilemma, Nash equilibrium, Nash’s theorem on the existence of equilibrium.

4. Cooperative games, the core and the Shapley value. Nash bargaining problem, voting rules and social choice.

Background material:

Game theory alive by Anna Karlin and Yuval Peres (available on-line).

In addition I may use material from several books in Hebrew by Maschler, Solan, Zamir, by Hefetz, and by Megiddo (based on lectures by Peleg). (If only I will manage to unite with my books that are not here.) We will also use a site by Ariel Rubinstein for playing games and some material from the book by Osborne and Rubinstein.

Requirement and challenges:

  • Play, play, play games, in Ariel Rubinshtein site and various other games.
  • Solve 10 short theoretical problem set.
  • Final assignment, including some programming project that can be carried out during the semester.
  • Of course, we will experience on-line study which is a huge challenge for us all.

Games and computers

  • Computer games
  • Algorithms for playing games
  • algorithmic game theory:
    • Mechanism design
    • Analyzing games in tools of computer science
    • Electronic commerce
  • Games, logic and automata: there will be a parallel course by Prof. Udi Boker

I still have some difficulty with the virtual background in ZOOM.

Posted in Combinatorics, Computer Science and Optimization, Economics, Games, Rationality, Teaching | Tagged , | 1 Comment

TYI44: “What Then, To Raise an Old Question, is Mathematics?”

“The argument is carried out not in mathematical symbols but in ordinary English, there is no obscure or technical terms. Knowledge of calculus is not presupposed. In fact, one hardly need to know how to count. Yet any mathematician will immediately recognize the argument as mathematical.” 

Test your intuition 44: what is the argument? who and where wrote this view about “what is mathematics”.

Zero-knowledge answers please.

Comments regarding this view itself and on “what is mathematics” are also welcome.

(Here are other posts on “What is mathematics.”)

 

 

PS. The last facetious sentence was omitted in the Journal version of the paper. (Indeed it was a good decision to take it out.) PPS Yannai Gonczarowski pointed out the the journal formulation is also rather condescending (perhaps even more so) towards non-mathematicians.

Posted in Test your intuition, What is Mathematics | Tagged , | 10 Comments

Kelman, Kindler, Lifshitz, Minzer, and Safra: Towards the Entropy-Influence Conjecture

Let me briefly report on a remarkable new paper by Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra, Revisiting Bourgain-Kalai and Fourier Entropies. The paper describes substantial progress towards the Entropy-Influence conjecture, posed by Ehud Friedgut and me in 1996. (See this blog post from 2007.)

Abstract: The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is o(logn), however, both results become useless when the total influence of the function is ω(logn). The only case in which this logarithmic barrier has been broken for an interesting class of function was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of S_n.

In this paper, we revisit the key ideas of the Bourgain-Kalai paper. We prove a new general inequality that upper bounds the correlation between a Boolean function f and a real-valued, low degree function g in terms of their norms, Fourier coefficients and total influences.

Some corollaries of this inequality are:

  1. The Bourgain-Kalai result.
  2. A slightly weaker version of the Fourier-Entropy Conjecture. More precisely, we prove that the Fourier entropy of the low-degree part of f is at most O(I[f]log^2 I[f]), where I[f] is the total influence of f. In particular, we conclude that the Fourier spectrum of a Boolean function is concentrated on at most 2O(I[f]log^2 I[f]) Fourier coefficients.
  3. Using well-known learning algorithms of sparse functions, the previous point implies that the class of functions with sub-logarithmic total influence (i.e. at most O(\log n/(\log \log n)2)) is learnable in polynomial time, using membership queries.

Our theorem on influence under symmetry. From my videotaped lecture on Jean Bourgain. See this post about Jean Bourgain.

A few remarks:

A) Given a Boolean function f:\{-1,1\}^n\to \{-1,1\} let f=\sum_{S \subset \{1,2,\dots ,n\}}\hat f(S)W_S be its Fourier-Walsh expansion. (Here W_S(x_1,x_2,\dots ,x_n)=\prod_{i\in S}x_i.) The total influence I(f) of f is described by

I(f)=\sum {S \subset \{1,2,\dots ,n\}}\hat f^2(S)|S|.

The spectral entropy E(f) of f is defined by

E(f)=\sum_{S \subset \{1,2,\dots ,n\}}\hat f^2(S) \log (\hat f^2(S)).

The entropy-influence conjecture (here called the Fourier-entropy conjecture) asserts that for some universal constant C

I(f) \ge C E(f).

B) One interesting feature of the conjecture is that the RHS is invariant under arbitrary linear transformations of \{-1,1\}^n (regarded as an n-dimensional vector space) while the LHS is invariant only to permutations of the variables.

C) My paper with Jean Bourgain, Influences of variables and threshold intervals under group symmetries, describes lower bounds on total influences for Boolean function invariant under certain groups of permutations (of the variables). Those results are stronger (but more restrictive) than what the Entropy/influence conjecture directly implies. (This was overlooked for a while.) The new paper gives (much hoped for, see below) simpler proofs and stronger results compared to those in my paper with Jean Bourgain.

D) Ryan O’Donnel wrote about Bourgain and some of his contributions to the analysis of Boolean functions:

“I spent close to 5 years understanding one 6-page paper of his (“On the distribution of the Fourier spectrum of Boolean functions”), and also close to 10 years understanding a 10-page paper of his (the k-SAT sharp threshold ‘appendix’). If anyone’s up for a challenge, I’m pretty sure no one on earth fully understands the second half of his paper “Influences of variables and threshold intervals under group symmetries” with Kalai (including Gil 🙂 )”

It looks that by now we have pretty good understanding and even some far-reaching progress regarding all three papers that Ryan mentioned. (It is unclear if we can hope now for an exponential spread of understanding for Bourgain’s proofs.)

 

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , , | Leave a comment

Or Ordentlich, Oded Regev and Barak Weiss: New bounds for Covering Density!

Barak Weiss lectured about his breakthrough results with Or Ordentlich, and Oded Regev, at a Simons Institute workshop: Lattices: Geometry, Algorithms and Hardness.

It is a famous problem what is the densest (or, most efficient) packing of unit balls in Euclidean n-dimensional spaces and, of course, you can ask the same questions for other convex bodies. A sort of a dual problem, also famous, is the question of the most efficient covering the n-dimensional Euclidean space by balls or by translates of other convex bodies.

A very basic insight is that covering is much more efficient than packing. Can you explain the reason for that? The only thing that came up to my mind was that convex sets are roundish from the outside but not from the inside which makes it easier to cover with them.

But how efficiently can we cover the n-dimensional Euclidean space with translates of a convex body $K$?

C.A. Rogers with coauthors had some very fundamental results regarding covering (and packing) in the 50s and 60s. Or Ordentlich, Oded Regev and Barak Weiss have made a terrific improvement for one of the main questions in this area. They showed that for every convex set K, you can find a lattice of determinant 1, and r>0  such that rK+L = \mathbb R^n and

{\rm vol} (rK) \le cn^2.

The best earlier upper bound was n^{\log \log n}.

One surprising aspect of the proof is the use of finite field Kakeya-type questions. Since the breakthrough by Zeev Dvir, many people had hopes for applications from the finite fields results to the Euclidean setting (in particular, to the Euclidean Kakeya problem itself) and it is rare to see such applications. The proof here relies on results by  Dvir, Kopparty, Saraf, Sudan, and Lev. The Ordentlich-Regev-Weiss paper is not yet on the arXiv but the lecture gives a good picture about the results and the proofs.

The definition of the covering density of L with respect to a convex body K

The definition of the covering density of K

Old results for the Euclidean ball

Old results for general convex bodies

The first main result

 

The required finite field Kakeya theorem.

Posted in Combinatorics, Computer Science and Optimization, Geometry | Tagged , , | 2 Comments

To cheer you up in complicated times – A book proof by Rom Pinchasi and Alexandr Polyanskii for a 1978 Conjecture by Erdős and Purdy!

Things do not look that good, and these are difficult times. But here on the blog we have plenty of things to cheer you up and assure you. And today we point to two book proofs — two book proofs to the same theorem– and, as a matter of fact, two book proofs to the same theorem by the same person, Rom Pinchasi.  One of the proofs, the one chosen for presentation, is by Rom Pinchasi and  Alexandr Polyanskii.

Rom Pinchasi has an immense proving power, both for difficult proofs at all costs, for book proofs, and for a large variety of proofs in between. (See, for example,  this post.)

Before moving on, let me mention that there is a timely blog post by Terry Tao on Online teaching, and here is a related MO question about online conferences that I asked last December.

Proofs from the book

Famously, the mathematician Paul Erdős, often referred to “The Book” in which God keeps the most elegant proof of each mathematical theorem. During a lecture in 1985, Erdős said, “You don’t have to believe in God, but you should believe in The Book.” (And you do not have even to believe in the book to enjoy proofs from the book.)

The Theorem: a 1978 conjecture by Erdős and Purdy

Theorem:  Let P be a set of n points in general position in the plane. Suppose that R is a set of red points disjoint from P such that every line determined by P passes through a point in R. Then |R|≥ n for n > 6.

This theorem settles a problem by Erdős and Purdy from 1978. Erdős and Purdy also asked about the case where the set of points is not required to be in general position. For that problem the best known lower bound, also proved by Rom Pinchasi, is n/3.

Book Proof I: An algebraic solution of a problem of Erdős and Purdy, by Rom Pinchasi

Book Proof II: A one-page solution of a problem of Erdős and Purdy, by Rom Pinchasi and Alexandr Polyanskii

Murty’s magic configurations conjecture.

The first proof of the Erdős-Purdy 1978 Conjecture was achieved in 2008 by Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, and Günter Rote. They derived it from their solution to the 1971 conjecture on magic configurations by Murty. A planar set of points P is called magic if it possible to assign positive weights to the points so that the sum of weights in every line determined by the points is one. Murty conjectured that the only magic configurations are those in general position, and those which have a line missing at most one of the points, and a certain configuration of seven points.

The Pinchasi-Polyanskii Book-Proof:

Here, we very closely follow the Pinchasi-Polyanskii’s paper.

We say that a line is determined by a set of points in the plane if it contains at least two of the points. Since the points in P are in general position, each pair of points determines a different line.

Under the contrary assumption we must have |R| = n−1. Then it must be that every point in R is incident to precisely n/2 lines determined by P and every line determined by P is incident to precisely one point in R. We would like to reach a contradiction.

Preliminary step: apply a projective transformation to the plane such that the convex hull of P becomes a triangle.

Observation 1:  No point of R lies outside the convex hull of P.

Such a point r should be incident to two lines supporting the convex hull of P. Each of these supporting lines must contain precisely two points of P. Since the convex hull of P is a triangle this is impossible.

Regard the points in the plane as complex numbers.

(This is really cool. I am not aware of many examples in discrete geometry that thinking about planar points as complex numbers helps.)

Notation: for every point p in the plane we denote by p_x  the x-coordinate of p.

Crucial definition: For every point p ∈ P define

f(p) = \prod_{r \in R}(p-r) / \prod_{p' \in P\backslash \{p\}}(p-p').

Observation 2: f(p) is a real number!

The proof will surely make you smile: For every p’ ∈ P \{p} there is a unique r ∈ R such that p, p’, and r are collinear. So (p-r)/(p-p’) is real. And the big ratio between products split to many small fractions that are all real.  Walla!

Note that f(p) is thus also invariant under rotations of the plane.

Now, if the vertical line through p does not contain any other point in P ∪ R, then, for the unique r ∈ R such that p, p’, and r are collinear, we have that:

(1)~~~(p-r)/(p-p')~=~(p_x-r_x)/(p_x-p'_x).

This leads to:

Observation 3:  if the vertical line through p does not contain any other point in P ∪ R, then

(2)~~~ f(p) = \prod_{r \in R}(p_x-r_x) / \prod_{p' \in P\backslash \{p\}}(p_x-p'_x).

Crucial observation 4:  Let p and q be any two points in P and let r be the unique point in R collinear with p and q. Then

f(p)/f(q)=-(p-r)/(q-r).

To see this rotate the plane so that the x-coordinates of p,q, and r are equal (or nearly equal) and apply Equations (2) and (1). (You will get the same, or nearly the same, contributions for r’ ≠ r  and you are left with the contribution for r. ) This also leads to:

Observation 5: f(p)/f(q) >0  if and only if the unique point r ∈ R that is collinear with p and q lies in the straight line segment delimited by p and q.

A complete graph with green and red edges.

Consider the complete graph G whose vertices are the points in P. For every two points p, q ∈ P we color the edge connecting  p and q red if the unique point in R collinear with p and q lies outside the straight line segment connecting p and q. Otherwise we color the edge green. In other words, the edge is red if f(p)/f(q) < 0, and green if f(p)/f(q) > 0.

The vertices of G can naturally be partitioned into two sets: U = {p ∈ P | f(p) > 0} and W = {p ∈ P | f(p) < 0}.

Without loss of generality assume that the three vertices of the convex hull of P belong to U. (Since no point of R is outside this convex hull all edges of the triangle forming the convex hull are green.)

Observation 6: |U| = n/2 + 1.

To see this let a,bU be two vertices of the convex hull of P. Let cR be the point in R collinear with a and b. The point c must be between a and b on the boundary of the convex hull of P. Therefore, all the other n/2 −1 pairs of points of P that are collinear with c must form red edges. Consequently, precisely one point of every such pair belongs to U. Together with a and b, we obtain |U| = n/2+1.

End of proof:

Continue reading

Posted in Combinatorics, Geometry, What is Mathematics | Tagged , | 8 Comments

A new PolyTCS blog!

A new PolyTCS blog

The PolyTCS Project is a new blog to run collaborative Theoretical Computer Science projects. The initiative is by two graduate students Rupei Xu and Chloe Yang. The logo was designed by Grigory Yaroslavtsev.

At this stage the blog raised possible projects to pursue.  A few days ago Rupei Xu discussed a second possible exciting project:   Project 2: Is Semi-Definite Programming (SDP) Polynomial-Time Solvable? The first project-proposal (Nov 1, 2019 by Jiapeng Zhang) was Project 1: The Entropy-Influence Conjecture.

(Here is a 2014  post on GLL on the problem of Project 2, and here is my 2007 post on WN on the problem of Project 1.)

Good luck!!!

 

Posted in Combinatorics, Computer Science and Optimization, Mathematics over the Internet | Tagged , , | Leave a comment

Remarkable New Stochastic Methods in ABF: Ronen Eldan and Renan Gross Found a New Proof for KKL and Settled a Conjecture by Talagrand

 

The main conjecture from Talagrand’s paper on boundaries and influences was settled by Ronen Eldan and Renan Gross. Their paper introduces a new powerful method to the field of analysis of Boolean functions (ABF).

This post is devoted to a new breakthrough paper by Ronen Eldan and Renan Gross, Concentration on the Boolean hypercube via pathwise stochastic analysis.

The paper introduces remarkable new techniques based on stochastic calculus, (that bypass the use of hypercontractivity), that allow to settles several open problems on analysis of Boolean functions. (And on the way, to give a very different proof for KKL.)

Renan Gross recently wrote an excellent high-level explanation of the paper in his  blog: New paper on arXiv: Concentration on the Boolean hypercube via pathwise stochastic analysis. It is accompanied by a brief introduction to Boolean analysis, featuring the required Boolean material:

 

Before we move on, a trivia question:

Trivia question: Who invented the term hypercontractivity?

(For a hint, see at the end of the post.)

Back to the paper by Ronen Eldan and Renan Gross. Perhaps the best way to explain what was achieved in this paper is to put one after the other the abstracts of the first version followed by the abstract of the second paper.

 

Ronen and Renan’s paper. Version 1, 26 Sept 2019.

The title for version 1 was: Stability of Talagrand’s influence inequality

And here is the abstract: 

We strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function

(1)~~~~~\mathrm{var}\left(f\right)\leq C\sum_{i=1}^{n}\frac{\mathrm{Inf}_{i}\left(f\right)}{1+\log\left(1/\mathrm{Inf}_{i}\left(f\right)\right)}

where  \mathrm{Inf}_{i}\left(f\right) denote the influence of the i-th coordinate. We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial (KKL) inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary. Our proofs rely on new techniques, based on stochastic calculus, and bypass the use of hypercontractivity common to previous proofs.

Let me say a few words about it. KKL theorem asserts that the maximal influence of a balanced Boolean function is at least \Omega (\log n/n) var (f). The famous tribe example of Ben-Or and Linial shows that this is tight.  The KKL paper gave some statements about other norms of the influence vector and Talagrand’s inequality stated above (from the paper “On Russo’s 0-1 law”) gives a sharp description of the influence vectors. Ronen and Renan found a new method that gave new proofs for KKL’s theorem and the stronger Talagrand’s inequality. This new methods led to new stability result.

Now, lets move to version 2.

Ronen and Renan’s paper: Version 2: 12 Nov 2019,

Ronen Eldan and Renan Gross, Concentration on the Boolean hypercube via pathwise stochastic analysis.

Abstract: We develop a new technique for proving concentration inequalities which relate between the variance and influences of Boolean functions. Using this technique, we

1. Settle a conjecture of Talagrand [Tal97] proving that

(2)~~~~~\int_{\left\{ -1,1\right\} ^{n}}\sqrt{h_{f}\left(x\right)}d\mu\geq C\cdot\mathrm{var}\left(f\right)\cdot\left(\log\left(\frac{1}{\sum\mathrm{Inf}_{i}^{2}\left(f\right)}\right)\right)^{1/2},

where h_f(x) is the number of edges at x  along which f changes its value, and Inf_i(f) is the influence of the i-th coordinate.

2. Strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function f

\mathrm{var}\left(f\right)\leq C\sum_{i=1}^{n}\frac{\mathrm{Inf}_{i}\left(f\right)}{1+\log\left(1/\mathrm{Inf}_{i}\left(f\right)\right)}

We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary.

3. Improve a quantitative relation between influences and noise stability given by Keller and Kindler.

Our proofs rely on techniques based on stochastic calculus, and bypass the use of hypercontractivity common to previous proofs.

Let me explain in a few words the main inequality that verified a conjecture by Talagrand. For other advances look at the paper itself.

The famous Margulis-Talagrand inequality asserts that

(3)~~~~~\int_{\left\{ -1,1\right\} ^{n}}\sqrt{h_{f}\left(x\right)}d\mu\geq C\cdot\mathrm{var}(f).

Let me say a little more. Talagrand’s proved in  his paper on Influence and boundary asserts that the right hand is a constant only if II(f) – the sum of squares of the influences is a constant. He conjectured that we can actually add the square root of \log II(f) to the RHS.

A few remarks:

  1.  For more background see my old post “Nati’s influence“.
  2. Let me mention that Talagrand’s influence inequality (Equation (1) above) is sharp up to a multiplicative constant. This is shown in a 2015 paper: On the Converse of Talagrand’s Influence Inequality by Saleet Klein, Amit Levi, Muli Safra, Clara Shikhelman, and Yinon Spinka.
  3.  Finding the best constant in KKL’s theorem is a well known challenge. So is the question of understanding balanced Boolean functions on n variables where the maximum influence is C \log n/n. Ehud Friedgit in his paper: Influences in Product Spaces, KKL and BKKKL Revisited, have made important conjectures for such Boolean functions.
  4.  I expect that the new method will have many applications. Ronen Eldan in a paper Second-order bounds on correlations between increasing families, found applicaions to correlation inequalities which I will discuss at some other time.
  5.  See the last part of this post for a description of Talagrand’s various relevant papers.
  6. Renan Gross is building the BooleanZoo in a similar spirit to the famous complexityZoo.
  7. I was in the process of writing a post about progress on ABS, mentioning twelve or so papers, apologizing for not mentioning others, promising to write in details about some of the papers, and making further apologetic remarks. But as this large post does not advance let me start with some of the promises.

talabb

Hint to the trivia question:

Continue reading

Posted in Analysis, Combinatorics, Probability | Tagged , , | 5 Comments

Hoi Nguyen and Melanie Wood: Remarkable Formulas for the Probability that Projections of Lattices are Surjective

Following a lecture by Hoi Nguyen at Oberwolfach, I would like to tell you a little about the paper: Random integral matrices: universality of surjectivity and the cokernel by Hoi Nguyen and Melanie Wood.

Two background questions:

Hoi started with two background questions –

Background Question 1: Consider an n \times n 0-1 matrix where the entries are taken at random. What is the probability that the matrix is singular (over the rationals)?

Hoi mentioned the recent result of Konstantin Tikhomirov, and moved to talk about matrices over the integers.

Background Question 2: Now, think about the lattice spanned by the rows of the matrix. How likely it is that this is the full \mathbb Z^n? (In other words that the determinant is +1 or -1.)

Probably, I thought, the answer is less than exponentially small.

The main question

Hoi moved quickly to the main question

Main question: Now think about the rows of a random 0-1 (n+1) \times n matrix. How likely it is that this is the full \mathbb Z^n?

Hmm, I was not sure how quickly the answer should tend to zero. But I learnt quickly that the answer does not tend to zero at all!

A remarkable heuristic formula: the probability for a random integral matrix from (n+1)-dimensions to n-dimenssions to be surjective is

one over  (ζ(2)ζ(3)ζ(4)ζ(5)…) 

What would justify this formula? Hoi described the following heuristic argument.

  1. To be surjective you need to be surjective modulo p for every prime number p.
  2.  Take some p. The probability to be surjective modulo p when the entries are uniformly random (independently) numbers modulo p is \prod_{j=2}^{n+1}(1-p^{-j}).
  3. This probability continues to work if you consider 0-1 entries.
  4. You can assume that all these probabilities for different primes are statistically independent.
  5. When you multiply all these probabilities you get

\zeta(2)^{-1}\zeta(3)^{-1}\zeta(5)^{-1}\zeta(7)^{-1}\cdots

When Hoi reached this formula in his Oberfolfach lecture my immediate thought was this: This is a remarkable formula; maybe it is even true although it looks very hard to justify the two crucial steps  in the heuristics. Why you can assume that 0-1 matrices behave like random matrices with uniform entries and why we have statistical independence that allows us to multiply probabilities just like in high school probability class? And maybe it is not true.

(This heuristics is known as the Cohen Lenstra heuristics and it was made for understanding the structure of class groups of quadratic fields.)

And then came the next slide of the presentation.

 

Hoi Nguyen and Melanie Wood actually proved this formula!

This is  a special case of a considerably more general formula. Look at the paper for more details and for the proofs.

It looks to me that the proof is tour de force and it uses various difficult and delicious techniques and earlier results. Various new and old Littlewood-Offord type results which are independently interesting are used.

And here is a related paper by Hoi and Melanie: Cokernels of adjacency matrices of random r-regular graphs.

 

Little more

As mentioned in the Nguyen-Wood paper, Shaked Koplewitz   roposed and proved some cases the Cohen-Lenstra heuristic for integral n by n+k matrices. (See Skaed’s comment below.)

As for background problem 2, the paper mentioned that the fact that the probability tends to 0 follows from Corollary 3.4 from a paper by Melanie Wood: Random integral matrices and the Cohen Lenstra Heuristics.  (Maybe there are different avenues for showing that there is a vanishing probability for every specific value of the determinant as well.) I don’t know if it is known that the probability that the determinant is 1 is exponentially small. (You can guess it is like square root of n! or something like that.) Also I don’t know if the ratio between the probabilities that the determinant is 3 and that it is 7 respects the Cohen Lenstra heuristics. Do we expect it at all? You can regard the determinant as a strange random walk so what is the reason that stopping at 3 will be different than stopping at 7?  It is also not known and this is raised as a question in the paper if the probability that the determinant is a perfect square respects the Cohen-Lenstra heuristics (and this seems reasonable).

There are similar nice questions for simplicial complexes. See the paper Cohen–Lenstra heuristics for torsion in homology of random complexes, by Matthew Kahle, Frank Lutz, Andrew Newman, and Kyle Parsons.

So if you consider the torsion of the 7 dimensional homology of a random 14 dimensional manifolds. Then (unless there are theorems to the contrary) it is natural to guess that the torsion will obey a Cohen-Lenstra heuristic of some kind.  This also applies to rationally acyclic complexes (hypertrees) and various other gadgets.

 

Posted in Algebra, Combinatorics, Number theory, Probability | Tagged , | 6 Comments

Petra! Jordan!

Last week we had a lovely small workshop in Eilat organized by Nathan Rubin, and as possible since the peace agreement of 1994 between Israel and Jordan, we visited Jordan for one day and saw the spectacular ancient city of Petra. Here are some pictures from Petra and Eilat.

With Andreas Holmsen, Janos Pach, and Gabor Tardos.

  

And a couple pictures from Eilat

 

Posted in Uncategorized | Tagged , , | Leave a comment

The largest clique in the Paley Graph: unexpected significant progress and surprising connections.

The result on Paley Graphs by Hanson and Petridis

On May 2019, Brandon Hanson and Giorgis Petridis posed a paper on the arXive: Refined Estimates Concerning Sumsets Contained in the Roots of Unity. The abstract was almost as short as the title (the paper is short as well!):

We prove that the clique number of the Paley graph is at most \sqrt {p/2}+1, and that any supposed additive decompositions of the set of quadratic residues can only come from co-Sidon sets.

Let me elaborate on the first half of the abstract.

Let q be a prime power such that q=1 (\mod 4). This choice implies that in F_q the difference of two numbers, a-b, is a square iff -(a-b) is a square, so the Paley graph we are going to define is a simple graph.

In the Payley graph the vertices are the elements of F_q and two are adjacent iff their difference is a square.

When the field is F_p, where p is prime, then the Paley graph is conjectured to be an excellent construction for a Ramsey graphs, the largest complete subgraph (which has the same size as its largest empty subgraph since it is self-complementary) is conjectured to be \log(p)\log \log (p). This is actually a lower bound for infinitely many primes, proved by Montgomery under the assumption that the generalized Riemann hypothesis holds.

The upper bound (which is easy to prove) is \sqrt p. This upper bound is sharp for the field F_{p^2}. (This is a very nice construction of Aart Blokhuis.)

There was practically no improvement on the \sqrt p upper bound until 2013, when Bachoc, Ruzsa and Matolcsi, proved that the \sqrt p-1 bound holds for infinitely many primes.

Hanson and Petridis thus improved the upper bound significantly! They gave the upper bound \sqrt{p/2}+1 on the clique size of the Paley graph. Their  proof uses Stepanov’s method.

The result of Di Benedetto, Solymosi, and White on directions in Cartesian products

A couple weeks ago, Daniel Di Benedetto, József Solymosi, and Ethan White posted a paper on the arxive: On the directions determined by a Cartesian product in an affine Galois plane. Also here the abstract is also quite short (and so is the entire paper!).

We prove that the number of directions contained in a set of the form A \times B \subset AG(2,p), where p is prime, is at least |A||B| -\min\{|A|,|B|\}+2. Here A and B are subsets of GF(p) each with at least two elements and |A||B|<p. This bound is tight for an infinite class of examples. Our main tool is the use of the Rédei polynomial with Szőnyi’s extension.

A surprising connection

Now, if you have a set A where the difference between any two elements is a square then in A \times A all directions, (a-b)/(c-d), are also squares. To Daniel, József, and Ethan’s  great surprise applying their bound on the clique number of the Paley graph gave the very same bound as Hanson and Petridis!

I am thankful to Józsi Solymosi for very helpful clarifications.

Payley graph with 13 vertices (source: wikipedea)

A quick Sum-Product update, and associations.

Now that I mention Józsi’s work let me also use this opportunity to give a quick update about Erdős-Szemeredi’s sum product conjecture. In an old post from 2009, I presented Elekes’ pioneering geometric proof for his sum-product world record and gave a link to a paper and a blog post written by Izabella Laba about József Solymosi’s new (then) world record. I just saw an article by Kevin Hartnett about the problem in Quanta Magazine describing several subsequent records. The current world record is in a 2019 paper by George Shakan.   (Sergei Konyagin and Ilya Shkredov broke József’s record in 2015, and the new record improved a 2016 world record by Misha Rudnev, Ilya Shkredov and Sophie Stevens; I also updated my related MO answer.) Of course, the sum-product phenomena is a huge area with amazing applications (See, here, here, here, and here; I recall that Jean Bourgain referred to it as a gold mine or something like that). Now, talking about sum-product theorems, and about Bourgain, and about Quanta Magazine, I should mention a lovely Quanta podcast featuring Alex Kontorovich interviewed by Steven Strogatz  .

Posted in Combinatorics, Number theory | Tagged , , , , , | 2 Comments