67
$\begingroup$

What are some examples of mathematical conjectures that applied mathematicians assume to be true in applications, despite it being unknown whether or not they are true?

$\endgroup$
  • 1
    $\begingroup$ What precisely do you mean by "being unknown whether or not they are true"? $\endgroup$ – Somos Jan 18 '18 at 22:58
  • 4
    $\begingroup$ @Somos As in, we do not have a valid proof or disproof of the conjecture. $\endgroup$ – PyRulez Jan 18 '18 at 22:59
  • 22
    $\begingroup$ Do physicists qualify as "applied mathematicians"? There are hundreds of unproved conjectures that physicists believe. $\endgroup$ – Alexandre Eremenko Jan 19 '18 at 3:34
  • $\begingroup$ @AlexandreEremenko Eh, probably close enough, as you don't make hundreds of answers. $\endgroup$ – PyRulez Jan 19 '18 at 3:37
  • $\begingroup$ This is tangential to the question, but perhaps might be of interest: "When were mathematical conjectures first formulated and communicated?." $\endgroup$ – Joseph O'Rourke Jan 22 '18 at 0:37
74
$\begingroup$

An important specific conjecture is that you cannot factor large integers fast. Many security systems for Internet and other transactions, depend on this.

$\endgroup$
  • 8
    $\begingroup$ Afaik, all (public key) cryptography algorithms boil down to some number theoretic conjecture. Not necessarily factoring large numbers, but something has to be assumed to be difficult. $\endgroup$ – Dustan Levenstein Jan 18 '18 at 23:36
  • 4
    $\begingroup$ I'm not an expert, but I think this is not true for Merkel hash-based schemes: "the European Commission has recommended use of Merkle signature scheme for long term security protection against quantum computers." $\endgroup$ – Joseph O'Rourke Jan 19 '18 at 0:11
  • 14
    $\begingroup$ It‘s Merkle by the way. No politics involved. $\endgroup$ – ThiKu Jan 19 '18 at 0:39
  • 4
    $\begingroup$ Isn't a Merkle tree just as secure as its underlying hash function? $\endgroup$ – darij grinberg Jan 19 '18 at 1:05
  • 1
    $\begingroup$ Even if P!=NP, factoring isn't known to be NP-hard, so crypto based on it could still be vulnerable even if we can't tackle NP problems in polynomial time. $\endgroup$ – Gray Taylor Jan 20 '18 at 22:51
47
$\begingroup$

It is an open problem to resolve a question formalized by G. Shephard in 1975:

Q. Can the surface of every convex polyhedron be cut along edges and unfolded flat to one non-self-overlapping polygon in the plane?

It is usually called Dürer's problem because there is a sense in which it goes back to Dürer. But I am not sure it is fair to call it a "conjecture," one reason this is not an ideal answer to the posed query.

It is also a bit of a stretch to claim there is a direct application. But I did find a Ph.D. thesis in mechanical engineering that lamented, "there is no theorem or efficient algorithm that can tell if a given 3D shape is unfoldable [without overlap] or not." Despite Dürer's problem being unresolved, any engineer or architect who wants to unfold a 3D shape—say, to punch it out of aluminum—breaks it into convex pieces (one piece if already convex), and easily edge-unfolds the pieces without overlap. The lack of a resolution to the open problem is no impediment to actually finding edge-unfoldings in practice.


               
                Fig. from Geometric Folding Algorithms, p.299: Soccer ball unfolding.


J.O'Rourke, "Dürer's problem." In Marjorie Senechal, editor, Shaping Space: Exploring Polyhedra in Nature, Art, and the Geometrical Imagination, pages 77--86. Springer, 2013. (Springer link.)

$\endgroup$
  • $\begingroup$ @Somos: You are quoting PyRulez, not me. I think what s/he means is that it is unknown whether or not the conjecture is true or false, or the open problem is resolved positively or negatively. The latter is the situation for Dürer's problem. $\endgroup$ – Joseph O'Rourke Jan 18 '18 at 22:55
  • 2
    $\begingroup$ Yes, sorry about that. Thanks for the clarification. $\endgroup$ – Somos Jan 18 '18 at 22:59
  • 22
    $\begingroup$ I find it incredible that this is an open problem. $\endgroup$ – Jim Conant Jan 19 '18 at 2:00
  • $\begingroup$ Some partial results are in this paper: erikdemaine.org/papers/Ununfoldable/paper.pdf $\endgroup$ – Timothy Chow Jan 19 '18 at 16:59
  • 6
    $\begingroup$ The paper Timothy cites proves that a particular non-convex polyhedron (a "spikey" tetrahedron) has no edge-unfolding that leads to a non-overlapping polygon in the plane. So it establishes that if the conjecture is true, it requires convexity. $\endgroup$ – Joseph O'Rourke Jan 22 '18 at 0:30
32
$\begingroup$

The Miller-Rabin primality test works very well in practice as a probabilistic algorithm for finding "practical" (not provable) primes in cryptography, but the algorithm would become an efficient polynomial-time deterministic algorithm if the generalized Riemann hypothesis is true for all Dirichlet $L$-functions (well, maybe just for even characters is enough). In practice I don't think anybody in cryptography cares about GRH being true or not in order to be content using this primality test precisely because of the probabilistic version of it that does not depend on GRH, so this example might not strictly be an answer to the original question, but I think it is a good approximation to an answer.

$\endgroup$
  • 8
    $\begingroup$ In particular, the probabilistic test is as good as the deterministic for applications, since with enough tests you can make it so the probability of error is the same as the probability of the deterministic test giving the wrong answer due to hardware errors. $\endgroup$ – PyRulez Jan 19 '18 at 1:33
  • $\begingroup$ Is the deterministic Miller-Rabin test actually used in practice? $\endgroup$ – Kimball Jan 19 '18 at 2:55
  • $\begingroup$ @Kimball no, the probabilistic test is what is used. $\endgroup$ – KConrad Jan 19 '18 at 4:09
  • 2
    $\begingroup$ Relatedly, we could prove better running times for the original version of the AKS primality test if some conjecture about the distribution of Sophie Germain primes holds. I'm not sure if later versions of AKS "depend" on that conjecture. $\endgroup$ – David Richerby Jan 19 '18 at 14:21
  • $\begingroup$ @Kimball In practice the Miller test is significantly slower than APR-CL and ECPP, and the latter don't require the GRH. This is not a complete surprise as ECPP and the Miller test are both $O(\log^{(4+\epsilon)}(n))$. Other than simplicity and theory there isn't much reason for us to pine for this. Later versions of AKS do not rely on Sophie-Germain primes -- both Pomerance/Lenstra and the much faster (non-randomized) Bernstein variants do not rely on this. The original and updated versions all run in empirical $O(\log^{(6+\epsilon)}(n))$ time (very different constants though). $\endgroup$ – DanaJ Jan 19 '18 at 22:00
31
$\begingroup$

The use of RSA for public-key encryption is widely believed to rely on the assumption that factoring is hard. Actually it relies on a stronger assumption than this, namely that the RSA problem is hard.

The RSA problem is the following: given a semiprime $N = pq$ and an exponent $e$ such that $\gcd(e, \varphi(N)) = 1$, efficiently compute $e^{th}$ roots $\bmod N$. It is widely believed that the only way to do this is to compute $e^{-1} \bmod \varphi(N)$ where $\varphi(N) = N - p - q + 1$, and in turn it is widely believed that the only way to do this is to factor $N$ so as to compute $\varphi(N)$. However, strictly speaking both of these are conjectures which are independent of the conjecture that factoring is hard.

So it may be that factoring is hard but that the RSA problem is easy because there is some clever way to avoid these steps and solve the RSA problem without factoring $N$. Note also that we only need to factor semiprimes; it may also be that factoring is hard but that factoring semiprimes is easy.

$\endgroup$
  • 4
    $\begingroup$ The math in RSA works not just for products of two distinct primes, but for any product of distinct primes (a single prime would lead to a really silly cryptosystem). So if factoring integers that are products of two primes winds up being easy without making factoring of squarefree integers with $k$ prime factors for some $k > 2$ also easy, then RSA could be saved by using $k$ primes instead of 2 primes. Admittedly, all known guidelines for avoiding easily cracked public keys in RSA would need to be adapted to products of $k$ primes. Someone should start working on that so we're ready. $\endgroup$ – KConrad Jan 19 '18 at 1:23
  • $\begingroup$ See P!=NP mathoverflow.net/a/291019/102169 $\endgroup$ – Luchostein Jan 19 '18 at 13:34
18
$\begingroup$

Navier Stokes equations are believed to be well-posed.

$\endgroup$
  • 6
    $\begingroup$ It would be best to cite the specific conjecture (instead of just stating it), and how it is used in applications. $\endgroup$ – PyRulez Jan 18 '18 at 23:00
  • 7
    $\begingroup$ Is this even true (as stated)? My impression is that many people believe that the N-S equations are not necessarily well-posed and that they might blow up in finite time, but not for 'real-world' data. $\endgroup$ – Steven Stadnicki Jan 18 '18 at 23:45
  • 6
    $\begingroup$ @StevenStadnicki Your point is exactly what i meant. The "applied mathematicians" believe that NS are well-posed for conditions that occur in applications. $\endgroup$ – Piyush Grover Jan 19 '18 at 1:13
  • 1
    $\begingroup$ The conjecture is that the strong (regular) solutions of the Navier Stokes equations are globally well posed if the initial data have finite energy. Jean Leray constructed (1934) global weak solutions. For the appropriate formulation see an article by C.Fefferman on the milennium problem EXISTENCE AND SMOOTHNESS OF THE NAVIER–STOKES EQUATION. Although mathematicians seem to be more excited on the NS, more interesting and physically reliable are Euler equations of incompressible fluids.. $\endgroup$ – Artur Jan 19 '18 at 9:06
  • 3
    $\begingroup$ I wonder if what people really believe in or rely on is something like, CFD simulations are a reasonable approximation to reality. Even if it turns out, mathematically, that NS has some pathological properties, it could turn out that nature doesn't quite obey NS after all. Nature could obey some well-behaved equations that are close to, but not exactly the same as, NS, and maybe CFD simulations are doing a good job of approximating the real equations. $\endgroup$ – Timothy Chow Jan 19 '18 at 15:55
16
$\begingroup$

Although we have a proof now, I suspect grocers had intuitively stacked oranges in the most efficient way prior to the proof of Kepler's conjecture. I don't know for sure if any grocer was an applied mathematician.

https://www.newscientist.com/article/dn26041-proof-confirmed-of-400-year-old-fruit-stacking-problem/

$\endgroup$
  • 12
    $\begingroup$ Most likely they were aware of Gauss' partial result for lattices... $\endgroup$ – James Smith Feb 2 '18 at 10:28
  • $\begingroup$ I love a problem I can relate to. (I finally get why everyone seems so interested in sphere packing :) $\endgroup$ – DukeZhou May 16 '18 at 3:45
14
$\begingroup$

I think the biggest example is $P \neq NP$. Security experts routinely assume this to be true when designing security algorithms. The correct functioning of millions of machines depend on this.

I think its also the biggest example because if someone proves it false, then, depending on the details of the proof, the applications literally stop preforming their intended function (or not, depending on the details of the proof).

$\endgroup$
  • 24
    $\begingroup$ I think you are confusing $P=NP$ with "we can efficiently solve all NP problems". $\endgroup$ – Carlo Beenakker Jan 18 '18 at 21:26
  • 11
    $\begingroup$ I second Carlo's comment. Just knowing that P=NP doesn't let us (for example) factor numbers effectively, for a variety of reasons. Among others, 1. the proof might not be constructive, so it doesn't give us a relevant algorithm, 2. the polynomial algorithm might have horrible constant which make it unusable in practice (that happened with AKS primality test, which, while polynomial time, is to this day too slow to be remotely efficient). $\endgroup$ – Wojowu Jan 18 '18 at 21:29
  • 8
    $\begingroup$ @CarloBeenakker That's why I said "depending on the details of the proof". $\endgroup$ – PyRulez Jan 18 '18 at 21:31
  • 4
    $\begingroup$ Of course this is your question and your rules, but my understanding of how the question is posed is that all that should matter is the conjecture itself, not hypothetical means of its (dis)proofs. By themselves, P=NP and its negation have basically zero impact on security, for reasons in my other comment. $\endgroup$ – Wojowu Jan 19 '18 at 8:24
  • 4
    $\begingroup$ @Bakuriu, you keep saying this, but you have never shared your results. These numbers you give are wildly different than any other published results. It is stunningly easy to write an incorrect AKS implementation that looks like it works, but isn't actually the AKS test. $\endgroup$ – DanaJ Jan 19 '18 at 22:03
12
$\begingroup$

Many cryptographic protocols are based on the problem which seem to be hard. Among them Discrete logarithm problem and its variants (Diffie–Hellman problem, Decisional Diffie–Hellman assumption, Elliptic Curve Discrete Logarithm Problem), Quadratic residuosity problem, lattice problems (Short integer solution problem, Shortest basis problem,...),...

$\endgroup$
11
$\begingroup$

Tonelli–Shanks algorithm needs quadratic nonresidue $n$ modulo prime $p$. If the extended Riemann hypothesis is true, then the first quadratic nonresidue $n_p$ is always less than $3(\log p)^2/2$ (Wedeniwski 2001) for $ p>3$. Under this assumption Tonelli–Shanks algorithm becomes polynomial. Probabilistic heuristics (presuming that each non-square integer has a 50-50 chance of being a quadratic residue) suggests that $n_p$ should have size $O( \log p )$. The best unconditional estimate (Burgess) is $n_p\ll p^\theta$ for any $\theta >1/4\sqrt e$.

See also extended discussion at The least quadratic nonresidue, and the square root barrier.

$\endgroup$
  • 1
    $\begingroup$ Which part of this are applied mathematicians using? $\endgroup$ – Gerry Myerson Feb 2 '18 at 4:38
  • $\begingroup$ @GerryMyerson Good upper bound on $n_p$ means that in this application one can search for $n_p$ looking at $n=2,3,\ldots$ $\endgroup$ – Alexey Ustinov Feb 2 '18 at 7:53
  • 1
    $\begingroup$ Sure, but why would an applied mathematician want to know the first quadratic nonresidue? $\endgroup$ – Gerry Myerson Feb 2 '18 at 7:58
  • $\begingroup$ @GerryMyerson Because it needed in Tonelli–Shanks algorithm. $\endgroup$ – Alexey Ustinov Feb 2 '18 at 8:41
  • 2
    $\begingroup$ OK, but what would an applied mathematician do with Tonelli-Shanks? $\endgroup$ – Gerry Myerson Feb 2 '18 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.