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

9 Answers 9

79
$\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$
9
  • 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$ Jan 18, 2018 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$ Jan 19, 2018 at 0:11
  • 15
    $\begingroup$ It‘s Merkle by the way. No politics involved. $\endgroup$
    – ThiKu
    Jan 19, 2018 at 0:39
  • 5
    $\begingroup$ Isn't a Merkle tree just as secure as its underlying hash function? $\endgroup$ Jan 19, 2018 at 1:05
  • 2
    $\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$ Jan 20, 2018 at 22:51
50
$\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$
5
  • $\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$ Jan 18, 2018 at 22:55
  • 2
    $\begingroup$ Yes, sorry about that. Thanks for the clarification. $\endgroup$
    – Somos
    Jan 18, 2018 at 22:59
  • 26
    $\begingroup$ I find it incredible that this is an open problem. $\endgroup$
    – Jim Conant
    Jan 19, 2018 at 2:00
  • $\begingroup$ Some partial results are in this paper: erikdemaine.org/papers/Ununfoldable/paper.pdf $\endgroup$ Jan 19, 2018 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$ Jan 22, 2018 at 0:30
39
$\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$
3
  • 6
    $\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, 2018 at 1:23
  • $\begingroup$ See P!=NP mathoverflow.net/a/291019/102169 $\endgroup$
    – Luchostein
    Jan 19, 2018 at 13:34
  • $\begingroup$ I know I'm being pedantic again but RSA is not "widely believed" to rely on this assumption, it is trivially proved to be broken if you have a fast factorization algorithm because then the private exponent d is easily calculated from the public key (n,e) using the exact same steps that the original issuer used, namely the extended Euclid's algorithm can be used to find d as the multiplicative inverse of e modulo φ(n) = φ(p)φ(q) = (p-1)(q-1), which is basically what you wrote, too. So, my point is that "reliance" is transitive here. $\endgroup$
    – Arne Vogel
    Oct 19, 2022 at 9:54
35
$\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$
5
  • 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$ Jan 19, 2018 at 1:33
  • $\begingroup$ Is the deterministic Miller-Rabin test actually used in practice? $\endgroup$
    – Kimball
    Jan 19, 2018 at 2:55
  • $\begingroup$ @Kimball no, the probabilistic test is what is used. $\endgroup$
    – KConrad
    Jan 19, 2018 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$ Jan 19, 2018 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, 2018 at 22:00
22
$\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$
2
  • 21
    $\begingroup$ Most likely they were aware of Gauss' partial result for lattices... $\endgroup$ Feb 2, 2018 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, 2018 at 3:45
20
$\begingroup$

Navier Stokes equations are believed to be well-posed.

$\endgroup$
8
  • 7
    $\begingroup$ It would be best to cite the specific conjecture (instead of just stating it), and how it is used in applications. $\endgroup$ Jan 18, 2018 at 23:00
  • 8
    $\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$ Jan 18, 2018 at 23:45
  • 7
    $\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$ Jan 19, 2018 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, 2018 at 9:06
  • 4
    $\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$ Jan 19, 2018 at 15:55
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 performing their intended function (or not, depending on the details of the proof).

$\endgroup$
15
  • 28
    $\begingroup$ I think you are confusing $P=NP$ with "we can efficiently solve all NP problems". $\endgroup$ Jan 18, 2018 at 21:26
  • 12
    $\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, 2018 at 21:29
  • 9
    $\begingroup$ @CarloBeenakker That's why I said "depending on the details of the proof". $\endgroup$ Jan 18, 2018 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, 2018 at 8:24
  • 5
    $\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, 2018 at 22:03
13
$\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$
1
10
$\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$
6
  • 1
    $\begingroup$ Which part of this are applied mathematicians using? $\endgroup$ Feb 2, 2018 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$ Feb 2, 2018 at 7:53
  • 1
    $\begingroup$ Sure, but why would an applied mathematician want to know the first quadratic nonresidue? $\endgroup$ Feb 2, 2018 at 7:58
  • 2
    $\begingroup$ OK, but what would an applied mathematician do with Tonelli-Shanks? $\endgroup$ Feb 2, 2018 at 11:13
  • 1
    $\begingroup$ @GerryMyerson It depends on the definition of "applied mathematician". $\endgroup$ Feb 2, 2018 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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