The polymath blog

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 B₁, B₂, …, B_n are n bases of an n-dimensional vector space V (not necessarily distinct or disjoint), then there exists an n × n grid of vectors (v_ij) such that

1. the n vectors in row i are the members of the ith basis B_i (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 n² elements, and one of the matroids is defined by the given set of n² 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 B_i.  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 I₁, …, I_n are independent sets with |I_i| = i for all i.  Call this a triangular system.  Then I claim that there exists a way of choosing a v_i from each I_i in such a way that J₁ := {v_i} is independent.  The proof is easy: We start with the forced choice v₁ ∈ I₁, and then note that by the independent set axiom, since |I₂| = 2, there must exist some v₂ ∈ I₂ that can be added to v₁ to produce an independent set of size 2.  Similarly, once v₁ and v₂ are chosen, it follows directly from the independent set axiom that we can add some v₃ ∈ I₃, and so on.  This proves the lemma.  Now, once J₁ has been constructed, we can imagine removing the elements of J₁ 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 J₂ that contains exactly one element from each I_i 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 n² given vectors in a grid with the elements of B_i 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 I₁, …, I_n, 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 I_i 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 I₁, …, I_n, 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 I_i 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.

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 with there is an
0-1 matrix matrix whose determinant equals .  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 . (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