The polymath blog

March 6, 2017

Rota’s Basis Conjecture: Polymath 12

Filed under: polymath proposals — tchow8 @ 11:18 pm

There has been enough interest that I think we can formally declare Rota’s Basis Conjecture to be Polymath 12. I am told that it is standard Polymath practice to start a new blog post whenever the number of comments reaches about 100, and we have reached that point, so that is one reason I am writing a second post at this time. I am also told that sometimes, separate “discussion” and “research” threads are created; I’m not seeing an immediate need for such a separation yet, and so I am not going to state a rule that comments of one type belong under the original post whereas comments of some other type belong under this new post. I will just say that if you are in doubt, I recommend posting new comments under this post rather than the old one, but if common sense clearly says that your comment belongs under the old post then you should use common sense.

The other reason to create a new post is to take stock of where we are and perhaps suggest some ways to go forward. Let me emphasize that the list below is not comprehensive, but is meant only to summarize the comments so far and to throw in a few ideas of my own. Assuming this project continues to gather steam, the plan is to populate the associated Polymath Wiki page with a more comprehensive list of references and statements of partial results. If you have an idea that does not seem to fit into any of the categories below, please consider that to be an invitation to leave a comment about your idea, not an indication that it is not of interest!

Matroids with No Small Circuits

I want to start with an idea that I mentioned in my MathOverflow post but not in my previous Polymath Blog post. I think it is very promising, and I don’t think many people have looked at it. Geelen and Humphries proved that Rota’s Basis Conjecture is true for paving matroids. In the case of vector spaces, what this means is that they proved the conjecture in the case where every (n – 1)-element subset of the given set of n2 vectors is linearly independent. It is natural to ask if n – 1 can be reduced to n – 2. I have not digested the Geelen–Humphries paper so I do not know how easy or hard this might be, but it certainly could not hurt to have more people study this paper and make an attempt to extend its results. If an oracle were to tell me that Rota’s Basis Conjecture has a 10-page proof and were to ask me what I thought the method was, then at this point in time I would guess that the proof proceeds by induction on the size of the smallest circuit. Even if I am totally wrong, I think we will definitely learn something by understanding exactly why this approach cannot be extended.

Independent Partial Transversals

Let me now review the progress on the three ideas I mentioned in my first blog post. In Idea 1, I asked if the n2 vectors could be partitioned into at most 2n – 2 independent partial transversals. A nice proof that the answer is yes was given by domotorp. Eli Berger then made a comment that suggested that the topological methods of Aharoni and Berger could push this bound lower, but there was either an error in his suggestion or we misunderstood it. It would be good to get this point clarified. I should also mention that Aharoni mentioned to me offline that he unfortunately could not participate actively in Polymath but that he did have an answer to my question about their topological methods, which is that the topological concepts they were using were intrinsically not strong enough to bring the bound down to n + 1, let alone n. It might nevertheless be valuable to understand exactly how far we can go by thinking about independent partial transversals. Ron Aharoni and Jonathan Farley both had interesting ideas along these lines; rather than reproduce them here, let me just say that you can find Aharoni’s comment (under the previous blog post) by searching for “Vizing” and Farley’s comment by searching for “Mirsky.”

Local Obstructions

Idea 2 was to look for additional obstructions to natural strengthenings of Rota’s Basis Conjecture, by computationally searching for counterexamples that arise if the number of columns is smaller than the number of rows. Luke Pebody started such a search but reported a bug. I still believe that this computational search is worth doing, because I suspect that any proof that Rota’s Basis Conjecture holds for all matroids is going to have to come to grips with these counterexamples.

Note that if we are interested just in vector spaces, we could do some Gröbner basis calculations. I am not sure that this would be any less computationally intensive than exhausting over all small matroids, but it might reveal additional structure that is peculiar to the vector space case.

Algebraic Geometry

There has been minimal progress in this (admittedly vague) direction. I will quote Ellenberg’s initial thoughts: “If you were going to degenerate, what you would need to do is say: is there any version of this question that makes sense when the basic object is, instead of a basis of an n-dimensional vector space V, a 0-dimensional subscheme of V of degree n which is not contained in any hyperplane? For instance, in 2-space you could have something which was totally supported at the point (0,1) but which was “fat” in the horizontal direction of degree 2. This is the scheme S such that what it means for a curve C to contain S is that S passes through (0,1) and has a horizontal tangent there.”

Let me also mention that Jan Draisma sent me email recently with the following remarks: “A possible idea would be to consider a counterexample as lying in some suitable equivariant Hilbert scheme in which being a counterexample is a closed condition, then degenerate to a counterexample stable under a Borel subgroup of GLn, and come to a contradiction. ‘Equivariant’ should reflect the action of GLn × (SnSnn). However, I have not managed to make this work myself, even in low dimensions. In fact, having a good algebro-geometric argument for the n = 3 case, rather than a case-by-case analysis, would already be very nice!”

Alon–Tarsi Conjecture

Now let me move on to other ideas suggested in the comments. There were several thoughts about the Alon–Tarsi Conjecture that the Alon–Tarsi constant LnevenLnodd ≠ 0 when n is even. Rebecca Stones gave a formula that, as Gil Kalai observed, equated the Alon–Tarsi constant with the top Fourier–Walsh coefficient for the function detn; i.e., up to sign, the Alon–Tarsi constant is

ΣA (–1)σ(A) det(A)n,

where the sum is over all zero-one matrices and σ(A) is the number of zero entries in A. This formula suggests various possibilities. For example one could try to prove that LnevenLnodd ≢ 0 (mod p) where p = 2n + 1 is prime, because in this case, det(A)n must be 0, 1, or –1. This would already be a new result for n = 26, and the case n = 6 is small enough to compute explicitly and look for inspiration. Luke Pebody posted the results of some computations in this case.

Another possibility, suggested by Gil Kalai, is to consider a Gaussian analogue. Instead of random zero-one matrices, consider random Gaussian matrices and try to understand the Hermite expansion of detn, in particular showing that the coefficient corresponding to all ones is nonzero. This might be easier and might give some insight.

Note also that in the comments to my MathOverflow post, Abdelmalek Abdesselam proposed an analogue of the Alon–Tarsi conjecture for odd n. I do not think that many people have looked at this.

Generalizations and Special Cases

Some generalizations and special cases of the conjecture were mentioned in the comments. Proving the conjecture for graphic matroids or binary matroids would be an enormous advance. There is a generalization due to Jeff Kahn, in which we have n2 bases Bij and we have to pick vijBij to form an n × n grid whose rows and columns are all bases. Another generalization was prompted by a remark by David Eppstein: Suppose we are given n bases B1, …, Bn of a vector space of dimension mn, and suppose we are given an n × n zero-one matrix with exactly m 1’s in every row and column. Can we replace each 1 in the matrix with a vector in such a way that the m vectors in row i are the elements of Bi and such that the m vectors in every column form a basis?

Juan Sebastian Lozano suggested the following reformulation: Does there exist a group G such that V is a representation of G and there exists giG such that gi Bi = Bi+1, and for every vector bB1,

span{g0b, …, gn – 1b} = V

where gi = gig1 and g0 is the identity?

Other Ideas

Fedor Petrov mentioned a theorem by him and Roman Karasev that looks potentially relevant (or at least the method of proof might be useful). Let p be an odd prime, and let V be the Fp-vector space of dimension k. Denote V* = V \ {0} and put m = |V*|/2 = (pk – 1)/2. Suppose we are given m linear bases of the vector space V

(v11, …, v1k), (v21, …, v2k), …, (vm1, …, vmk).

Then there exist pairwise distinct x1, …, xm, y1, …, ymV* and a map g:[m] → [k] such that for every i ∈ {1, …, m} we have yixi = vig(i).

Gil Kalai notes that the Alon–Tarsi conjecture is related to the coloring polynomial of a graph and asks if we can learn anything by considering more general polynomials such as

Π {(xiλexj) : i < j, {i,j} = eE(G)},

where the λe are weights associated to the edges e.

February 28, 2017

Blog theme changed

Filed under: planning — Terence Tao @ 5:19 pm

Update from Gil: I managed to retrieve rubric but the subtitle disappeared.

As you may have noticed, the layout of this blog has changed.  I was trying to address a request by one of the commenters here to try to enable the links to recent comments to change colour if they were clicked on; unfortunately I was not able to do so, and in the course of doing so managed to change the theme in such a manner that the original theme (“Rubric”, which has been retired by wordpress) is no longer recoverable.  I hope the new theme is not too jarring in design (it is the closest I could find to the original layout, which tried to maximise the width of the main posts in order to facilitate detailed comments).  If there are any experts in CSS, wordpress, and/or design who can help improve the layout, please feel free to add suggestions in the comments of this post. (In particular, if there is a way to widen the main portion of the blog further, please let me know.)

February 23, 2017

Rota’s Basis Conjecture: Polymath 12?

Filed under: polymath proposals — tchow8 @ 11:44 pm

This post tentatively kicks off Polymath 12 on Rota’s basis conjecture.

I proposed Rota’s basis conjecture as a possible Polymath project on MathOverflow last year. If you have not read my proposal, I strongly recommend that you read it now, because in it, I sketched some reasons why I thought this would make a good Polymath project, as well as some known partial results and potential avenues for progress.

Recently, I emailed several likely participants, and a number of them responded enthusiastically, enough in my opinion to warrant an attempt to start a Polymath project. I have discussed the possibility with the polymath blog admins and since I do not have a blog of my own, they have generously agreed to host the project here on the polymath blog itself. This means that you should comment freely in the comments section below.

Rota’s basis conjecture states that if B1, B2, …, Bn are n bases of an n-dimensional vector space V (not necessarily distinct or disjoint), then there exists an n × n grid of vectors (vij) such that

1. the n vectors in row i are the members of the ith basis Bi (in some order), and

2. in each column of the matrix, the n vectors in that column form a basis of V.

If this project gets enough momentum to be formally declared “Polymath 12” then it will be important to give a thorough summary of what is already known, and to lay out in some detail all the promising directions. However, at this early stage, I think that it is important to have some “quick wins” to get things moving, so I would like to present a couple of new ideas that I think could lead to some new partial results quickly, and also invite others to present their own ideas.

Idea 1

The first idea is to extend an old result of Aharoni and Berger that I think has not received too much attention from others.  Suppose we have two matroids on the same ground set E.  By definition, a common independent set is a subset of E that is independent in both matroids.  We can try to partition E into a disjoint union of common independent sets, and can ask the question, what is the smallest number β of common independent sets that we need?

Here is the relation to Rota’s basis conjecture.  The ground set E has n2 elements, and one of the matroids is defined by the given set of n2 vectors (here, if the same vector appears in more than one basis, we treat the different occurrences as being distinct).  The second matroid is the so-called transversal matroid whose independent sets are precisely those subsets of E that contain at most one element from each Bi.  From this point of view, Rota’s basis conjecture says that β = n, i.e., that E may be partitioned into n disjoint common independent sets (each necessarily of size n).

Aharoni and Berger have proved a general theorem about matroids that implies, in the specific case of Rota’s basis conjecture, that β ≤ 2n. They also have a very general conjecture on matroids that would imply that βn + 1 for Rota’s basis conjecture.

Let me now make the simple observation that it is easy to prove directly that β ≤ 2n – 1 for Rota’s basis conjecture.  We begin with a lemma. Suppose we have a matroid and suppose that I1, …, In are independent sets with |Ii| = i for all i.  Call this a triangular system.  Then I claim that there exists a way of choosing a vi from each Ii in such a way that J1 := {vi} is independent.  The proof is easy: We start with the forced choice v1I1, and then note that by the independent set axiom, since |I2| = 2, there must exist some v2I2 that can be added to v1 to produce an independent set of size 2.  Similarly, once v1 and v2 are chosen, it follows directly from the independent set axiom that we can add some v3I3, and so on.  This proves the lemma.  Now, once J1 has been constructed, we can imagine removing the elements of J1 from the original triangular system to obtain a smaller triangular system.  We can then repeat the argument on this smaller system to form an independent set J2 that contains exactly one element from each Ii for i = 2, 3, …, n. This shows that the original triangular system can be partitioned into (at most) n common independent sets (where as before, the second matroid is the natural transversal matroid).

Returning to the setup for Rota’s basis conjecture, we can write out the n2 given vectors in a grid with the elements of Bi in row i (not worrying about whether the columns are bases) and draw a diagonal to split the bases into two disjoint triangular systems, one of size n and one of size n – 1.  So we can partition the vectors into at most n + (n – 1) = 2n – 1 common independent sets, Q.E.D.

So the first question, which I don’t think has been looked at much and which hopefully should not be too hard, is:

Can we show that β ≤ 2n – 2?

Idea 2

In one of my papers I introduced the idea of looking for certain kinds of obstructions to an inductive proof of the conjecture. Specifically, suppose that instead of n bases, we are given n independent sets I1, …, In, each of size k < n. Suppose further that these nk vectors (counted with multiplicity) can be partitioned into k bases somehow (but not necessarily bases that contain exactly one vector from each row). Then we can ask if there exists an n × k grid whose ith row comprises the elements of Ii and whose columns are all bases. In general, the answer will be no, but it is not so easy to come up with counterexamples. I came up with two counterexamples with k = 2, but I think it would be worth doing a computational search for more examples. Even k = 2 and n = 5 has not been checked, as far as I know. If there are not many counterexamples then there is some hope that we could classify them all, and I think that this would be a big step towards proving the full conjecture. Note: one family of counterexamples has been identified by Harvey, Kiraly, and Lau.

Idea 3

The last idea I want to present here is very vague. It is inspired by a paper by Ellenberg and Erman that I recently learned about. The result of the paper itself isn’t relevant, but I thought that the method might be.  Roughly speaking, they reduce a certain combinatorial problem involving points and lines in a vector space to a “degenerate” case that is more tractable.  Since various “degenerate” cases of Rota’s basis conjecture are known, perhaps the same idea could be applied to extend those degenerate cases to more cases.

As an example of a known degenerate case, let us first generalize Rota’s basis conjecture slightly as follows. Let us allow the vector space V to have some dimension d > n, and instead of n bases, let us take any n independent sets I1, …, In, each of size n. Then we ask for the usual n × n grid except now we only require the columns to be independent and not necessarily bases. As far as I know, there is no known counterexample to this stronger conjecture. Moreover, this stronger conjecture is known to be true if we fix a single, standard basis B of V and insist that every Ii be a subset of B. Two proofs of this fact may be found in Section 2 of this paper.

Let me end this initial blog post here, with just one further comment that a couple of people that I have communicated with recently have some other concrete ideas that we can sink our teeth into immediately.  I am going to invite them to explain those ideas in the comments to this blog post.

August 13, 2016

MO Polymath question: Summary of Proposals

Filed under: polymath proposals — Gil Kalai @ 7:23 pm

mo

Here are the Math Overflow Polymath proposals given in response to the polymath question,

Summary of proposals (updated: August 10, 2016)

1) The LogRank conjecture. Proposed by Arul.

2) The circulant Hadamard matrix conjecture. Proposed by Richard Stanley.

3) Finding combinatorial models for the Kronecker coefficients. Proposed by Per Alexandersson.

4) Eight lonely runners. Proposed by Mark Lewko.

5) A problem by Ruzsa:
Finding the slowest possible exponential growth rate of a mapping from N to Z that is not a polynomial and yet shares with (integer) polynomials the congruence-preserving property n−m∣f(n)−f(m). Proposed by Vesselin Dimitrov.

6) Finding the Matrix Multiplication Exponent ω. (Running time of best algorithm for matrix multiplication.) Proposed by Ryan O’Donnell.

7) The Moser Worm problem and Bellman’s Lost in a forest problem. Proposed by Philip Gibbs.

8) Rational Simplex Conjecture ( by Cheeger and Simons). Proposed by Sasha Kolpakov.

9) determinants for 0-1 matrices Proving that for every integer m with |m|\le c(\sqrt{n}/2)^n there is an n \times n
0-1 matrix matrix whose determinant equals m.  Proposed by Gerhard Paseman.

10) Proving or disproving that the Euler’s constant is irrational. Proposed by Sylvain JULIEN.

11) The Greedy Superstring Conjecture. Proposed by Laszlo Kozma.

12) Understanding the behavior and structure of covering arrays. Proposed by Ryan.

13) The group isomorphism problem, proposed by Arul based on an early proposal by Lipton.

14) Frankl’s union closed set conjecture (Proposed by Dominic van der Zypen; Also one of the proposals by Gowers in this post). (Launched)

15) Komlos’s conjecture in Discrepancy Theory. Proposed by Arul.

16) Rota’s Basis Conjecture. Proposed by Timothy Chow.

17)+18) I contributed two proposals. One in ANT is to A problem in ANT show that
$latex 2^n+5$ is  composite for almost all positive integers n. (Might be too hard.) Another is to prove a remarkable combinatorial identity on certain Permanents.

19) Real world applications of large cardinals Proposed by Joseph van Name. There were a few more proposals in comments.

20) A project around a cluster of tiling problems. In particular: Is the Heech number bounded for polygonal monotiles? Is it decidable to determine if a single given polygonal tile can tile the plane monohedrally? Even for a single polyomino? Proposed by Joseph O’Rourke

February 7, 2016

Polymath 11 is Now Open

Filed under: news — Gil Kalai @ 3:45 am

PF      PF2

Two great Peter Frankls

Tim Gowers launched polymath 11 aimed at Peter Frankl’s conjecture asserting that for every union-closed family there is an element that belongs to at lease half the sets in the family. Here are links to Post number 0 and Post number 1. (Meanwhile polymath10 continues to run on “Combinatorics and More.”)

 

 

Polymath Proposals on Math Overflow

Filed under: news,polymath proposals — Gil Kalai @ 3:21 am

mo

 

Here is the link to a mathoverflow question asking for polymath proposals. There are some very  interesting proposals. I am quite curious to see some proposals in applied mathematics, and various areas of geometry, algebra, analysis and logic.

Explaining Polynomials Identities – Success!

Filed under: news — Gil Kalai @ 3:03 am

Thakur_color_150x210                                              DavidSpeyerCasual

Dinesh Thakur                                                                David Speyer

A beautiful polymath proposal by Dinesh Thakur was posted  by Terry Tao on the this blog. The task was to explain some remarkable, numerically observed, identities involving the irreducible polynomials P in the polynomial ring {\bf F}_2[t] over the finite field of characteristic two. David Speyer managed to prove Thakur’s observed identities! Here is the draft of the paper. Congratulations to Dinesh and David!

 

January 2, 2016

“Crowdmath” project for high school students opens on March 1

Filed under: polymath proposals — Terence Tao @ 4:25 pm
Tags: ,

The MIT PRIMES program and the Art of Problem Solving are planning to run a “Crowdmath” project for high school students with advanced mathematical backgrounds, based on the polymath approach to mathematical research.  The project, which officially starts on March 1, will be devoted to original research on a mathematics problem to be specified at the time of the project (but judging from the reference material provided, it will probably involve the combinatorics of 0-1 matrices).  Participation is open to all high school students (though they will need an Art of Problem Solving account).

December 28, 2015

Polymath proposal: explaining identities for irreducible polynomials

Filed under: planning,polymath proposals — Terence Tao @ 7:05 pm

I am posting this proposal on behalf of Dinesh Thakur.

Let F_2[t] be the ring of polynomials over the finite field F_2 of two elements, and let

\displaystyle {\mathcal P} = \{t, t+1, t^2+t+1, \dots \}

be the set of irreducible polynomials in this ring.  Then infinite series such as

\displaystyle \sum_{P \in {\mathcal P}} \frac{1}{1+P} = \frac{1}{t+1} + \frac{1}{t} + \frac{1}{t^2+t} + \dots

and

\displaystyle \sum_{P \in {\mathcal P}} \frac{1}{1+P^3} = \frac{1}{t^3+1} + \frac{1}{(t+1)^3+1} + \frac{1}{(t^2+t+1)^3+1} + \dots

can be expanded as formal infinite power series in the variable t = 1/u.

It was numerically observed in http://arxiv.org/abs/1512.02685 that one appears to have the remarkable cancellation

\displaystyle{}\sum_{P \in {\mathcal P}} \frac{1}{1+P} = 0

and

\displaystyle{}\sum_{P\in{\mathcal P}} \frac{1}{1+P^3}=\frac{1}{t^4+t^2}

\displaystyle = u^4 + u^6 + u^8 + \dots.

For instance, one has

\displaystyle \frac{1}{t+1} = u + u^2 + u^3 + \dots

\displaystyle \frac{1}{t} = u

\displaystyle \frac{1}{t^2+t} = u^2 + u^3 + \dots

and all other terms in \sum_{P \in {\mathcal P}} \frac{1}{1+P} are of order u^3 or higher, so this shows that {}\sum_{P \in {\mathcal P}} \frac{1}{1+P} has u-valuation at least 3.  Similarly, if one expands the first sum for all primes of degree (in t) up to 37, one obtains {}u^{38}+u^{39}+u^{44}+u^{45}+\dots (the calculation took about a month on one computer), implying that the u-valuation of the infinite sum is at least 38; in fact a bit of theory can improve this to 42. (But we do not know whether this 42  is the answer to everything!).

For the second sum, calculation for degrees up to 28 shows that the difference between the two sides has u-valuation at least 88.

The polymath proposal is to investigate this phenomenon further (perhaps by more extensive numerical calculations) and supply a theoretical explanation for it.

Background links:

Below the fold is some more technical information regarding the above calculations.

(more…)

November 6, 2015

Polymath10 is now open

Filed under: news — Gil Kalai @ 12:42 pm
Tags:

Sonnenblume_02_KMJ

 

Polymath10 has started on my blog. The aim is to prove the Erdos-Rado sunflower conjecture (also known as the delta-system conjecture).  Here is the wikipage.

Next Page »

Blog at WordPress.com.