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 Coca-Cola 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 “return-policy.”
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, cook-outs, 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 knock-off of something already on the market, but here goes. Fix a composite number , and consider this variation on circuits with unbounded fan-in 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.
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 sub-determinants of . Then . The same goes for the set of sub-determinants, any .
- The are the sub-permanents 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 sub-permanents would take about 100 years on the hardware he had. So he ran with the sub-permanents, and after 37-1/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 sub-determinants , , 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 sub-determinants, and the simple proof is that the sub-determinants 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 solution-set sizes in Volker Strassen’s lower-bound theorem, which we covered here. But this got falsified for a family of constant-degree polynomials with linear-size circuits whose -many first partial derivatives combine to make minimal monomials. Hence this idea is part of our sale.
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.