July Fourth Sale Of Ideas
All ideas on sale—most 50% off
Asa Candler invented the coupon in 1895. Candler, a pharmacist by trade, later purchased the CocaCola company from the original inventor Dr. John Pemberton, also a pharmacist. Candler created the notion of coupons to help promote his new drink. He later became the mayor of Atlanta.
Today Ken and I want to talk about a special July Fourth Sale on mathematical ideas. All ideas are 50% off, this holiday through the weekend.
We made up a coupon that is good for 50% off on all ideas this Fourth of July.
Since we usually charge zero for what we tell you, it is also 100% off. We hope that you will still value the ideas even though they are on sale. As is usually the case we make no warranty on how useful these ideas are—all sales are final. No refunds of any kind. We do however allow you to send in your own ideas as comments, so think of that as a “returnpolicy.”
About Today
July Fourth in the USA is our celebration of independence. It is an official holiday commemorating the adoption of the Declaration of Independence on July 4, 1776, which separated us from the UK.
There are many important traditions on this day: parades, fireworks, cookouts, and more. One that I like since I grew up in the New York City area is the annual Nathan’s Hot Dog Eating Contest in Coney Island, which started in 1916. Their hot dogs are great, but I could only eat a couple.
Of course most nations have yearly celebrations like the 4th of July is for the US. In France it is the 14th of July, in India the 15th of August, and in Mexico it is the 16th of September—but the Mexicans celebrate Cinco de Mayo on May 5th. Ken’s family once celebrated Quebec’s National Day (Fête St.Jean) in Quebec City on June 24, with fireworks on the Plains of Abraham battle site.
I found the following question and answer on the web:
 When did July 4th start?
 The 4th of July started on July 4th, 1776.
But it is wrong. It seems a joke to say July 4 started with the guy who invented the calendar, but it’s actually true—and he even got July named after himself.
Okay not too funny, so let’s move on to our ideas that are on sale today.
Ideas On Sale
Factoring: This is still one of my favorite problems. At the Princeton Turing meeting I asked Peter Sarnak directly what he believed and he immediately answered: “it is obviously in polynomial time.” This will be hard to solve, of course, but there seems to be an intermediate idea that he started. Consider
where is an “easy” to compute integer function, and is the Möbius function. Can we show that this tends to zero as goes to infinity? For functions from this was resolved beautifully by Ben Green—see here. There are two ideas on sale:
 Try to extend his result to a larger class of functions. I believe that even is still open.

The other approach is to try and show that the sum will not go to zero for functions that are sufficiently powerful. For even polynomial time computable functions we cannot show that it does not tend to zero. Note that if is the indicator function for the primes, then the expression goes to zero only as
But can we do better? This seems to be an approachable problem.
Lonely Runner: I have discussed this problem before here and previously. Can we extend the ideas there by using triples instead of pairs of runners? I believe that this should be worked out. Actually I would love someone to step up, grab the coupon for this problem, and help write a full paper.
Jacobi Circuits: These may just be a knockoff of something already on the market, but here goes. Fix a composite number , and consider this variation on circuits with unbounded fanin Boolean and modulo gates. The input wires to a gate may carry values 1 as well as 0 or 1, so that their sum can be negative. For Boolean gates 1 is the same as 1, but the mod gates compute the Jacobi symbol
where is the unique prime factorization of , and for prime , is the Legendre symbol giving 0 if is a multiple of the prime , otherwise +1 or 1 according as is a quadratic residue mod or not.
For polynomial size and constant depth, are these just the same as circuits? They could be more general, but could also be more restricted. We haven’t looked at the warranty very closely—besides, it’s in French.
Our last sale item needs its own section.
Manic Monomials
Minimal Monomials: If you are given polynomials in variables , can you combine them to make a monomial? By combine we mean finding polynomials to use as multipliers and forming the expression
When can you make a monomial, and how many different monomials can you make this way? Note that if is a monomial multiple of , then you can make too by defining for each , so the question is really how many monomials can you make that are minimal with this property—no proper divisor of can be made.
It follows from theorems of David Hilbert that the number of minimal monomials is always finite. Actually there is a sense, namely measure in the real or complex space of coefficients of terms of the , in which the number is almost always zero. Here are two important cases when and is the matrix of variables:
 The are the subdeterminants of . Then . The same goes for the set of subdeterminants, any .
 The are the subpermanents of . Then is not . In fact it is gigantic as a function of .
How gigantic? No one knows. For Ken did a computation that found at least 2,196 minimal monomials. For Ken estimated that the analogous computation with the subpermanents would take about 100 years on the hardware he had. So he ran with the subpermanents, and after 371/4 days he found about 128,000 minimal monomials. Fireworks indeed.
For a simple example with the permanent, consider
Then yields the monomial . Whereas for the subdeterminants , , and , the analogous expression using a positive multiplier on the second one cancels everything away. Curiously it is completely impossible to get any monomials from subdeterminants, and the simple proof is that the subdeterminants form a Gröbner basis, which (in reduced form) always has at least one monomial if there are any.
Clearly this is a wild structural difference between the permanent and determinant. But what can be proved with it? Ken thought could be a lower bound on arithmetical complexity analogous to the log of solutionset sizes in Volker Strassen’s lowerbound theorem, which we covered here. But this got falsified for a family of constantdegree polynomials with linearsize circuits whose many first partial derivatives combine to make minimal monomials. Hence this idea is part of our sale.
Open Problems
Our sale items also have an optional service agreement with us. Does that influence you to buy them?
Will this July 4th also be remembered for Higgs fireworks?
Have a safe and fun Fourth if celebrating it, and if not have a safe day anyway.
Nice post as usual.
Question: Do people consider computation with polynomial ideals over ? This paper http://www.math.ucdavis.edu/~deloera/RECENT_WORK/jsc09_issac08.pdf suggest the algorithm to find infeasibility certificate for the polynomial system. On the other hand, Lasserre relaxation show how to check if system is feasible. The combination of two can guarantee the answer – feasible/not feasible. One can create an ideal that accept only 0 and 1, e.g. plus additional equations that restricts possible 01 solutions – encoding the problem in the ideal of polynomials. The advantage, is that this system is testing all solution space at once, similar to quantum computers. Moreover, the intermediate results does not have to be unique, and be represented by the null space of possible monomial values. For example, is it possible to represent the Quantum Fourier transform in this way, and use the resulting null space for “interference” through the additional set of polynomials. More specifically, whether it is possible to write the system of polynomials in , such that ideal in of this system is Fourier transform of the integer n, and than add additional polynomials that restrict the ideal to be the encoding of factors of n.
Proving Mobius randomness for the RudinShapiro sequence will already be a major breakthrough!
http://mathoverflow.net/questions/97261/mobiusrandomnessoftherudinshapirosequence
In more details: Let where are the digits in the binary expansion of .
, the th term of the Rudin Shapiro sequence is defined by
The question is:
Prove that
Re: the lonely runner. There are known extensions of the probabilistic method that might apply here. I believe that these methods are not well known, since I have not seen any other potential application, but they are described in “Generalized Bonferroni inequalities” in the Journal of Applied Probability 1994, pp 409417.
I no longer have easy access to this paper, so I do not remember exactly what it said. However, it dealt with the following situation. Let $Z=\sum X_i$, where the $X_i$ are 01 random variables that are not necessarily independent. Then let $S_1 = \sum Pr(X_1=1)$, $S_2=\sum_{i < j} Pr(X_i=1 and X_j=1)$, and so on. We want to bound probability that $Z=0$ based on the$Sk$. The probabilistic method says that if $S_1 0$. It is also known that if $S_1S_2+S_30$. There are potentially stronger results in the cited paper.
I believe that there is a very simple solution to the lonely runner conjecture which proves it to be true for any n, without making any assumptions concerning the runners speeds etc. It was just recently that i came across the problem. However, it was related to something that i gave consideration to a number of years back. I am an engineer and not a mathematician so whilst the explanation of the solution is as easily stated as the problem itself i am not in a position to explain it using strictly mathematical formalism. I would be interested to share this idea. email details are provided.