The polymath blog

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.

September 22, 2015

The Erdős discrepancy problem has been solved by Terence Tao

Filed under: polymath5 — Gil Kalai @ 12:41 pm
Tags: ,

Polymath5 was devoted to the Erdős discrepancy problem. It ran in 2010 and there were a few additional posts in 2012, without reaching a solution. The problem has now been solved by Terry Tao using  some observations from the polymath project combined with important recent developments in analytic number theory. See this blog post  from Tao’s blog and this concluding blog post from Gowers’s blog.

January 20, 2014

Two polymath (of a sort) proposed projects

Filed under: discussion,polymath proposals — Gil Kalai @ 5:20 pm
Tags: , ,

This post is meant to propose and discuss a polymath project and a sort of polymath project.

I. A polymath proposal: Convex hulls of real algebraic varieties.

One of the interesting questions regarding the polymath endeavor was:

Can polymath be used to develop a theory/new area?

My idea is to have a project devoted to develop a theory of “convex hulls of real algebraic varieties”. The case where the varieties are simply a finite set of points is a well-developed area of mathematics – the theory of convex polytopes, but the general case was not studied much. I suppose that for such a project the first discussions will be devoted to raise questions/research directions. (And mention some works already done.)

In general (but perhaps more so for an open-ended project), I would like to see also polymath projects which are on longer time scale than existing ones but perhaps less intensive, and that people can “get in” or “spin-off” at will in various times.

II. A polymath-of-a-sort proposal: Statements about the Riemann Hypothesis

The Riemann hypothesis is arguably the most famous open question in mathematics. My view is that it is premature to try to attack the RH by a polymath project (but I am not an expert and, in any case, a project of this kind is better conducted with some specific program in mind). I propose something different. In a sort of polymath spirit the project I propose invite participants, especially professional mathematicians who thought about the RH over the years,  to share their thoughts about RH.

Ideally each comment will be

1) One or a few paragraphs long

2) Well-thought, focused and rather polished

A few comments by the same contributors are also welcome.

To make it clear, the thread I propose is not going to be a research thread and also not a place for further discussions beyond some clarifying questions. Rather it is going to be a platform for interested mathematician to make statements and expressed polished thoughts about RH. (Also, if adopted, maybe we will need a special name for such a thing.)

____________________

This thread is not launching any of the two suggested projects, but rather a place to discuss further these proposals. For the second project,  it will be better still if the person who runs it will be an expert in the area, and certainly not an ignorant. For the first project, maybe there are better ideas for areas/theories appropriate for polymathing.

Next Page »

Create a free website or blog at WordPress.com.