45
$\begingroup$

Is there any conjecture or famous unsolved problem, that doesn't require much prerequisite knowledge and could be plausibly proven / solved by freshman?

My hero is average freshman in mathematics, that proves a famous conjecture by mistaking it for homework, like George Dantzig.

Maybe something in combinatorics if this reddit comment is true

A few years ago at my university the final test on combinatorics included some unsolved problems. The students were supposed to have enough insight to realize which problems were the easy solvable ones and which ones were a waste of time to try to solve.

One of the students (this course is usually taken by first or second year students) actually solved one of the unsolved problems. It wasn't one of the really famous unsolved problems included on the test, but his result was certainly unknown.

The conclusion was somewhat less dramatic, though: the professors thought about his solution for some time (months) and after they were convinced that there isn't a loophole in the argument, the result was published and eventually became the basis for this guy's PhD. research.

Problems in combinatorics are certainly easier to approach on this level, since their solution usually involves some clever trick, rather than extensive application of deep theorems.

$\endgroup$
  • 4
    $\begingroup$ Unsolved, I will just write that it was solved / proven by my protagonist $\endgroup$ – ragac Nov 3 at 20:26
  • 14
    $\begingroup$ Being a fan of Dirk Gently, the Moving Sofa Problem is one of my favorites. $\endgroup$ – We are Monica. Nov 3 at 20:35
  • 3
    $\begingroup$ List of unsolved problems in mathematics, dear old Wikipedia. $\endgroup$ – AlexP Nov 3 at 20:37
  • 22
    $\begingroup$ For heaven's sake don't ask this at Math.SE. You will be downvoted into oblivion. Over the years we have seen to me "I wanna-be-famous-by-proving-this" posts containing nothing but non-sense. It gives people pimples. $\endgroup$ – Jyrki Lahtonen Nov 4 at 11:06
  • 4
    $\begingroup$ Shortest superpermutations are another good one. Was only a year ago that a better upper bound on the length of the shortest superpermutation of n states was found. I'm pretty sure we have already found the shortest possible superpermutation for n = 4, and even if the sequence was already known in the setting of your story, having someone construct it from first principles would be impressive. $\endgroup$ – Draco18s Nov 4 at 16:50
27
$\begingroup$

Others have mentioned some famous conjectures such as the Collatz conjecture and P = NP, but I think it's awfully unlikely that a freshman math student would be able to solve such a problem. About the Collatz conjecture, Paul Erdős famously said that "Mathematics may not be ready for such problems"; and about P = NP, Scott Aaronson wrote that "any proof will need to overcome specific and staggering obstacles" and "we do have reason to think it will be extremely difficult."

Instead, I suggest a Diophantine equation. A Diophantine equation is simply any polynomial equation (that is, an equation built out of variables, constants, addition, subtraction, and multiplication), where the question is, "Can we make this equation true by setting each variable to a whole number?"

A simple example of a Diophantine equation is $x^2 + y^2 = 5$. This Diophantine equation has 8 solutions. One of them is $x = 2$ and $y = 1$. The other 7 solutions can be found by switching $x$ and $y$ around, and by negating one or both of them.

It certainly is plausible that a Diophantine equation could baffle mathematicians for years, but then be solved by a freshman math student. And I have an anecdote to prove it!

In 1969, D. J. Lewis wrote a paper about Diophantine equations, in which he wrote that the equation $x^3 + 5 = 117 y^3$ is known to have at most 18 solutions, but the exact number is not known. Two other mathematicians studied the equation and, in 1971, they published a short but difficult proof that there are no solutions. Finally, in 1973, another mathematician found an astonishingly simple proof of the same fact! The proof is:

The quantity $x^3 + 5$ is never a multiple of 9, but the quantity $117 y^3$ is always a multiple of 9, so there are no solutions.

(Source for the above two paragraphs: Gerry Myerson's answer on "Awfully sophisticated proof for simple facts.") Gerry points out that Lewis's equation, as printed, may have been a typo.)

So, although this particular equation was never famous, it did give some mathematicians quite a bit of difficulty, before, years later, someone found a simple proof that easily could have been found by a freshman math student.

So, which Diophantine equation should you use in your story? The paper "Some open problems about diophantine equations" contains one in particular which I think looks pretty promising. The problem that your hero solves could be:

Find all integer solutions to $x^4+x^2+y^4+y^2=z^4+z^2$.

$\endgroup$
  • 4
    $\begingroup$ And of course, the fictional proof in the story can't be so simple that the author would be expected just to exhibit it to the reader ;-) $\endgroup$ – Steve Jessop Nov 4 at 23:17
  • 1
    $\begingroup$ You may be correct about P = NP, but I would not be particularly surprised by some amateur finding a solution to the Collatz conjecture. Erdős only meant that we hadn't yet developed the right tool set to systematically investigate the conjecture. However, all that would be required to solve that particular problem is someone playing around and happening to notice a pattern that no one before had noticed. That isn't an unreasonable thing to happen, and is pretty much the same as happened with your $x^3 + 5 = 117y^3$ example. $\endgroup$ – Paul Sinclair Nov 5 at 17:33
  • 7
    $\begingroup$ In case anyone else is also initially confused about the "x³+5 is never a multiple of 9" part, this helped me: If n is an arbitrary number divisible by 9, you can somewhat easily convince yourself by looking at it on paper that the results in the range of (n+1)³%9 to (n+8)³%9 are 0, 1, 8, 0, 1, 8, 0, 1, 8. After that it loops back, so you only ever have those remainders and plus 5 it's 5, 6, 13→4, 5, 6, 4, 5, 6, 4, …. $\endgroup$ – Fabian Röling Nov 5 at 18:19
  • 8
    $\begingroup$ While the 117 thing is cute, it is also misleading. It was probably a typo (no proof of the "at most 18 solutions" was given). Someone took it seriously as a problem and didn't try a simple method (hence the complex proof). Then someone else said "wait a second". If the problem was "famous" you wouldn't have every mathematician making the blunder the first "proof" producer did. $\endgroup$ – Yakk Nov 5 at 20:26
  • 2
    $\begingroup$ @Yakk That's true. Realistically, if a problem has already been tackled by hundreds of mathematicians with bulldozers and cannons, it's unlikely that a student will be able to solve it with a screwdriver and a BB gun. So I'm hoping that a less-than-famous unsolved problem will do the trick. $\endgroup$ – Tanner Swett Nov 6 at 1:25
52
$\begingroup$

Since you're interested in something currently unsolved, you don't really care about how protagonist will solve it, only that he does so, let's go for something extremely simple, simple enough that even a reader with only basics of mathematics can understand: Collatz conjecture (also known as 3n + 1 Conjecture)

"Consider the following operation on an arbitrary positive integer:

If the number is even, divide it by two.

If the number is odd, triple it and add one.

...

Now form a sequence by performing this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next.(Or in human language - keep repeating the previous process with new number again and again and again...)

...

The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially."

This is simple looking, yet currently unsolved problem, which looks simple enough for a reader who doesn't understand too much math as something solvable by a genius student.

A real student of mathematics or a professor will, reading your fiction, probably exclaim "That's not how it works, it's basically sure thing that any proof of this conjecture, if this conjecture is even provable, will be hundreds of pages long!"

But most of the audience will not find anything wrong with your protagonist solving this on ~6 pages as a homework. Only thing that might cause suspension of belief is that the guy has never heard of this conjecture before and confused it for homework.

$\endgroup$
  • 10
    $\begingroup$ It's a pity the OP didn't ask about the solved problems. I was about to go seek the problems appropriate for each era, starting with the proof of the existence of irrational numbers for the ancient era, cubic equations solution for the 16th century, and then also mention modern mathsci.fandom.com/wiki/The_Haruhi_Problem solved by anon from 4chan $\endgroup$ – Failus Maximus Nov 3 at 20:59
  • 46
    $\begingroup$ You don't even need a 6 page proof - you just need one example number that doesn't reach 1 because it goes into a loop. $\endgroup$ – Jerry Jeremiah Nov 3 at 22:54
  • 3
    $\begingroup$ Colltz might be proved in just a couple pages if the proof links together a couple existing hefty proofs. Think about if Weil’s work unifying various domains had come before Taniyama Conjecture. Fermat might have been solved easily if Weil hadn’t realized the ramifications of his modularity work. $\endgroup$ – SRM - Reinstate Monica Nov 3 at 23:02
  • 2
    $\begingroup$ @Mast It would be proving it to be false, which is just as good. $\endgroup$ – Omegastick Nov 4 at 14:48
  • 9
    $\begingroup$ @JerryJeremiah To nitpick: You would still have to give the number and show that it is indeed a proper counterexample. As far as I understand there are known lower bounds on the size of a circle, which depend on the size of numbers involved. And since anything small has been checked by computer, your counterexample would either involve a theoretical proof of its existence or listing a sequence of the hundred of thousands 20+ digit numbers which form a cycle, neither of which would come in below 6 pages. $\endgroup$ – mlk Nov 4 at 15:43
20
$\begingroup$

Goldbach's conjecture states that every even integer greater than two can be written as a sum of two primes. If one could find a counterexample the problem would be solved (although currently all candidates smaller than the order of 10^18 have been tried). Alternatively if one could give a formula the problem could also be solved.

$\endgroup$
  • $\begingroup$ My first thought. It's so "obvious" ... yet unproved. $\endgroup$ – nigel222 Nov 5 at 14:47
19
$\begingroup$

A perfect number is a positive integer N such that N is the sum of its divisors (other than itself). For example,

6 = 1 + 2 + 3

28 = 1 + 2 + 4 + 7 + 14

Question: Does there exist an odd perfect number?

$\endgroup$
  • 4
    $\begingroup$ Easy to answer in the affirmative just by finding an example. Hard to prove I’m the negative. $\endgroup$ – SRM - Reinstate Monica Nov 3 at 22:54
  • 2
    $\begingroup$ @SRM I wouldn't exactly call it "easy". $\endgroup$ – Priska Nov 3 at 22:55
  • 9
    $\begingroup$ No. But a student might plausibly luck into one. An easy proof mechanism exists as the basis for story. $\endgroup$ – SRM - Reinstate Monica Nov 3 at 23:14
  • 4
    $\begingroup$ @SRM I agree it's more plausible than many other problems (and one can suspend disbelief for stories). But it's not as simple as you make it sound: such conjectures have been thought about by many really smart people and tested numerically for numbers in a really big range. $\endgroup$ – Kimball Nov 4 at 9:07
  • 8
    $\begingroup$ @SRM When you say "just finding an example", we know that any such example will have at least 300 digits (people have computationally checked all smaller numbers); so it's well within the bounds of a bignum package on a PC - but it's still going to be quite a bit of work to check. $\endgroup$ – Martin Bonner supports Monica Nov 4 at 14:10
12
$\begingroup$

You already have some good answers here, but let me suggest one other possibility that might work for you. Rather than an unsolved problem, you might look at a couple of cases in which there is a proof of something that can be stated simply, but the proof is unsatisfying in some way. Either the proof is so complex that it is accessible only to (extreme) specialists, or the proof is so vast that a computer is required to manage it.

Fermat's Last Theorem is in the first category and The Four Color Theorem is in the second. When I was a young mathematician, both of these were (widely believed) conjectures, but unproven. Now they have proofs.

But a simple proof of either, a proof whose details can be easily grasped by, say, a college student (and doesn't require a computer), would, itself, be a breakthrough.

$\endgroup$
  • 1
    $\begingroup$ Of course, the beauty of Fermat's Last Theorem is that it already WAS solved by an amateur - albeit an incredibly gifted one, but the proof was lost. Maybe your freshman could just rediscover Fermat's proof...? $\endgroup$ – Lefty Nov 4 at 16:30
  • 8
    $\begingroup$ @Lefty, we don’t know whether Fermat proved it, only that he said he had proved it. Being gifted doesn’t make one immune to error (nor to falsehood). $\endgroup$ – WGroleau Nov 4 at 17:44
  • 2
    $\begingroup$ @UlrichSchwarz Excellent! If only my accidental joke was deliberate, it would have been SOOOO clever. It must have been subconscious. Yes, that's what it was. Definitely. I can prove it, but there's not enough space left in th $\endgroup$ – Lefty Nov 4 at 21:07
  • 2
    $\begingroup$ I wonder whether Fermat's proof ever existed. I suspect some time later he realized it was in error, or incomplete, and forgot to go back and erase his famous marginal note. Or if incomplete despite his best efforts, left it on purpose as bait for future generations of mathematicians. $\endgroup$ – nigel222 Nov 5 at 14:50
  • 4
    $\begingroup$ @Lefty Fermat was good, but the suspicion is that he found one of a number of known "proofs" that actually have subtle flaws. $\endgroup$ – Martin Bonner supports Monica Nov 5 at 18:02
11
$\begingroup$

The biggest unsolved problem in computing is “can NP-Complete problems be solved in polynomial time?” NPC problems are a whole class of searching problems that we hit regularly in real world operations. Polynomial time basically means “a reasonable amount of time even on large problem sets”.

Most researchers think the answer is “no.” Proving “no” is really hard. Proving “yes” on the other hand just requires someone writing the program that does it. The student might not even realize they’ve done anything amazing.

If you do have your protagonist solve this problem, it’ll be a pretty serious kick in the pants for performance of all computing tech in your world.

$\endgroup$
  • 2
    $\begingroup$ Note that other major algorithms have come from students and casual programmers just needing something to work. This isn’t without precedent. $\endgroup$ – SRM - Reinstate Monica Nov 3 at 22:51
  • 2
    $\begingroup$ @alexp Maybe. There’s good arguments why it might wouldn’t. See here for some: security.stackexchange.com/questions/12802/… $\endgroup$ – SRM - Reinstate Monica Nov 3 at 23:21
  • 12
    $\begingroup$ I agree it would cause panic and studying. The nightmare scenario would be a non-constructive proof. “I found that an algorithm must exist, but I don’t know what it is.” Then you’d have decades of everyone suspicious of everyone else and bluffing that “we have the decryptor!” Wouldn’t that be a frustrating world! $\endgroup$ – SRM - Reinstate Monica Nov 3 at 23:29
  • 5
    $\begingroup$ I see a few difficulties here. One, P = NP is so famous that he should’ve heard of it. Two, you can’t really explain the problem in a way that someone who’s never studied the theory of algorithms could get anywhere and write something that a computer scientist would agree is a rigorous proof of time complexity. Three, that’s notorious as a problem that crackpots think they’ve solved. Four, if the proof were in any way practical and not just of theoretical interest, the real-world and even philosophical consequences—for cryptography, AI, etc.—would be drastic. $\endgroup$ – Davislor Nov 4 at 8:54
  • 9
    $\begingroup$ @Davislor In response to points One, Two and Three: you could plausibly set a CS student a task to write a program that solves a NP-complete problem, and then when their solution is being graded, the professor looks at it, thinks "this is clever", looks at it some more and realises it's polynomial time. It's not quite the same as the request in the question, but it's pretty close. $\endgroup$ – Christopher Nov 4 at 17:40
2
$\begingroup$

To add on to the list of statements that are simple to understand: The Twin Primes Conjecture.

"Twin primes" are pairs of primes that differ by $2$, like $3$ and $5$, or $11$ and $13$. The open question is "Are there infinitely many pairs of twin primes?"

$\endgroup$
2
$\begingroup$

I would argue: any problem that can be conveyed simply without excessive higher-level math would be fair game.

Keep in mind, solving a conjecture/problem often doesn't depend on extreme math proficiency, but being able to creatively approach the problem from an unusual angle that hasn't been attempted before.

Here's a great example, from the 2011 International Math Olympiad. It was given to the brightest students in the world, yet this problem stumped most of them. And it wasn't because the problem required extreme proficiency with mathematics, but reaching an understanding of a core dynamic of how the system worked - and then simply exploiting part of that dynamic. The actual 'math' of the situation is almost an afterthought.

So let me give you some hypothetical examples:

"Yeah, I solved the 3 body physics problem. I mean, I know we were supposed to integrate over position, but that wasn't working out for me. So I tried to integrate over time and distance squared and I figured out that a lot of the complexity just disappears."

...

"Yeah, I solved the Collatz Conjecture. I thought to myself: why use a solid base? I mean, instead of each digit representing a constant number to an increasing power, why not make the digits correspond to prime numbers? So the number '3011' really represents 3x5+1x2+1x1. And when you look at the patterns in that number scheme? The patterns are pretty obvious - the conjecture is pretty trivially obvious."

...

"Oh, RSA decryption? Yeah, the whole 'Cannot find large factors' seemed kinda weird. I mean, we can express the large number in whatever base we want, right? So why not convert that large number into each of the first dozen or so prime bases. Then we guess at the lowest significant digits of the solution in each of those bases, correlate all those prime bases' guesses together, and get a pretty accurate picture for what the divisor must be."

Note: None of those hypotheticals are actually true. But it shows how an oblique, non-standard approach to a problem might be what actually 'cracks' the conjecture.

$\endgroup$
1
$\begingroup$

I would go with finding a non-trivial zero to Riemann's Zeta function, thus effectively proving (by counterexample) that Riemann's Hypothesis is false.

Pick a solution with the form $n/(2n+1)+xi$, with insanely large $n$ and very large but nice looking $x$.

Make it such that it is possible to simply check that the solution is indeed a zero of the Zeta function, thus the student would be easily believed, as false solutions to the problem pop-up very often, and even checking a correct proof could take years.

This problem fits two things that are nice for a narrative:

  1. It is said that the one to solve this problem is destined to mathematical greatness.
  2. Even a wrong or fuzzy method could still provide a verifiable non-trivial solution, and thus it wouldn't take long before the consequences of the discover start taking place.

The downsides are:

  1. It is a rather complex conjecture to be understood by someone who only knows about high-school math. (probably most of the potential audience)

  2. The hypothesis is widely believed to be true. (though it being proven false would have a much bigger impact).

Another "solution" would be finding a polynomial algorithm to find hash collisions for SHA2, as far as I know, there isn't a proof that such an algorithm would be impossible to exist, but a lot of cryptography based systems rely on the fact that it is too computationally expensive to create arbitrary hash collisions. This may or may not create different ramifications for the story, but it is something that a teacher wouldn't ask in a test as a "unsolved problem", it might be part of some research task to find methods that are better than brute-force (slightly, as has been done with other hashing algorithms), then by accident finding something much better than brute-force, or some algorithm that "just happens" to run fast very often, even if it could take very long (akin to Quicksort algorithm).

$\endgroup$

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.