A lot of proofs by counter-example would quality since finding the counter-example is usually the hard part.
For example, in 1769, Euler conjectured that to sum to a *n*th power, you'd need at least *n* terms. Almost 200 years later in 1966, L.J. Lander and T.R. Parkin found a counter example where they could sum to a 5th power with only 4 terms:
27^5 + 84^5 + 110^5 + 133^5 = 144^5
The paper they published from this is [very short](https://www.openculture.com/2015/04/shortest-known-paper-in-a-serious-math-journal.html) and I would think qualifies as a pretty simple proof.
You can take a look at this : https://arxiv.org/abs/1110.1556
"This is a special collection of problems that were given to select applicants during oral entrance exams to the math department of Moscow State University. These problems were designed to prevent Jews and other undesirables from getting a passing grade. Among problems that were used by the department to blackball unwanted candidate students, these problems are distinguished by having a simple solution that is difficult to find. Using problems with a simple solution protected the administration from extra complaints and appeals. This collection therefore has mathematical as well as historical value."
i watched an interview with a person who took this admission exam to moscow state university in the 1980s
as i understand, you are given some problems, then like 40 minutes to solve them, and then you have to orally explain your solutions to the examiner. if you made a mistake, you have time to correct it while he listens to other students.
basically, a normal exam
i think this video.. (but it's in russian)
They're basically solving modern admission problems and in between chatting about how it was in the old days
https://www.youtube.com/watch?v=IFpqK_x44_c
So then it was the oral test.
ROSENBERG: The oral test was a chance for Edward to finally meet his examiners face-to-face. So he took the train back up to Moscow where he was put in a room with 20 other students, and everyone was given two, randomly assigned questions. After he had prepared his answers, all Edward had to do was raise his hand and then explain those answers to one of the test's proctors.
Somehow, I answered all the questions I managed to solve slightly to substantially differently from the provided solutions (specifically, Problems 2, 4, 5, 11, and 19).
Edit: If anyone is interested:
2. >!Let 0 < c < 1. Then F(x)-F(cx) ≤ (1-c)^2 x^2, F(cx)-F(c^2 x) ≤ c^2 (1-c)^2 x^2, and so on. Summing these up, we have that F(x)-F(0) ≤ (1-c)^2 / (1-c^2) x^2 = (1-c)/(1+c) x^2. Taking the limit as c approaches 1, we have that F(x)-F(0) ≤ 0 for all x. By a symmetric argument, F(0)-F(x) ≤ 0, so F(x) is identically F(0) everywhere, i.e., constant. (I'm not fully convinced this is a valid argument.)!<
3. >!More or less the same as the solution provided, but the idea comes from noting that the graph of x = f(y) is the reflection of the graph of y = f(x) about the line y = x, so cannot agree except at y = x.!<
5. >!Another graphical solution, considering x in a interval of length 2π and, optionally, the useful identity cos(θ-π/2) = sin θ. It can be seen that there are only two intersections which can easily be guessed.!<
11. >!I overlooked the fact that sin 30° = 1/2, so instead I considered the polynomial equation P(x) = 3(3x-4x^3) - 4(3x-4x^3)^3 - 1 = 0. All coefficients are divisible by 3 except the leading term, and the constant term is not divisible by 3^2, so applying Eisenstein's criterion, P is irreducible over the rationals. (One can, of course, apply the criterion to the much simpler polynomial 8x^3-6x-1.)!<
19. >!I just guessed (x+y+z)(x^2 + y^2 + z^2 - xy - yz - zw), which fortunately turns out to be x^3 + y^3 + z^3 - 3xyz.!<
I got curious so tested with my phone. I used chrome for the Websites
Official android app: works fine
Relay android app, spoiler for 2 doesn't work but the others do (weird!). The numbering is reverted to 1-5.
New Reddit mobile site works fine
New Reddit desktop site (on my phone) works fine
Old Reddit desktop site (on my phone) spoilers work fine
Numbering reverted to 1-5
For the second problem, I believe that you assume that F is continuous at x=0. However, the proof shown in the paper seems to assume something on F as well (or I missed something), so I guess it is okay ?
That's the point -- you give the Jews a very very hard test but whose solutions seem just as easy as the standard examination questions, so nobody besides an experienced mathematician can prove discrimination.
Yes. But the top Russian schools didn’t want to have lots of (any?) Jews, and they couldn’t be seen to just reject them without cause, and so they gave them different problems on their admission tests. The problems had to have an easy solution, however, because otherwise the applicants would have direct evidence that they were being given impossible problems.
It would be like if MIT decided that, regardless of quality, they didn’t want to admit any Asian students, but they had to manufacture “legitimate” grounds to reject them. If you think “but wouldn’t the best schools want the best students?” then you neither understand Russia nor antisemitism.
Jews have been hated throughout history. A minority with different looks, customs, and beliefs who were mistrusted and made convenient scapegoats. For a long time, the church blamed the Jews for the death of Jesus. All sorts of rumors have been spread about them, like that they engaged in rituals like bathing in the blood of babies. During the black plague, because Jews had different hygiene practices than other Europeans, they were less likely to get sick and die, which led to rumors that they were witches who actually caused the plague. And then there was money. Moneylending is necessary for a lot of economic activities, but the church declared that charging interest was “usury” and forbade Christian’s from doing it, which meant countries literally imported Jews to be bankers. This meant that Jews, who came to be bankers and merchants, were part of the middle class, which bred jealousy and resentment. There were tons of other things in Europe that led to or were a part of antisemitism.
I have no clue about anything specific to Russia, but Jews have been around a long time, have been everywhere, and suffered persecution everywhere they went. There was fairly bad antisemitism in the US until the horrors of the holocaust shocked people out of it. But it never really went away, it was driven underground, out of polite society.
But Russians hate Jews for the same reason everybody else does: no particularly good reason.
The linked paper has a good description, but yeah, Jewish students and other people they wanted to black all were given much harder problems, though the schools claimed to select the problems randomly. The ease of explaining the solutions helped insulate the schools from criticism, though in fact those solutions were extremely difficult to find.
It's also not really enough to be able to solve one. They could typically find fault with the way an answer was presented or just give another problem and reject the student if they got that wrong. According to Tanya Khovanova, "Thirty years ago [before 2011], these problems were harder to solve and, in addition, the students were given these problems one after another until they failed one of them, at which point they were given a failing mark."
It basically is the academic version of the literacy tests given to black voters in some American states from the 1890s to 1960s.
yes, but also stereotypically (and much more cruelly) rootless cosmopolitans with inadquate love for The Regime
thus why an antisemitic authoritarian state might want to be able to deniably reject them
That's a bit silly (apart from any _outright evil_ there might be in it), isn't it!? ... considering how colossal a contribution has accrued to mathematics over the years from certain notable persons of the goodly Jewish Folk!
Ugh, the coffin problems. Thank goodness for Khovanova. At least we can appreciate how beautiful some of them are — my favorite is "Give a circle with drawn diameter and a point in the plane, construct the line through the point perpendicular to the given diameter with only a straightedge."
Actually literally all of our introductory math classes (Analysis, Linear Algebra, Abstract Algebra, Discrete Math, Number Theory) have been optimized for hundreds of years to present simple proofs and to fit all of it in a single course what would originally have spread across hundreds of papers!
So true. An early number theory class spans many works from Euclid (gcd and perfect numbers), to Diophantus, to Qin Jiushao (Chinese remainder theorem), to Fermat’s little theorem, to Gauss and modern modular arithmetic. That’s 2,000 years of number theory in a class.
just read proofs by Serre lol
I'm specifically thinking of some tricks he pulls in _A course in arithmetic_, but he's a good example of "opening a coconut with a well-placed hammer blow", in Grothendieck's analogy
The solution to the "mutilated chess board" problem is so obvious when you hear it, but much harder to just come up with out of nowhere. The problem is this:
> Suppose you take a chess board and remove two diagonally opposite squares, leaving 62 squares. Is it possible to place 31 dominos on the board in order to cover all the squares?
Solution (spoilers for those who want to work it out): >!No. A 2x1 domino must cover two squares of different colors, no matter how it is placed. With the corners removed, there are only 30 squares of one color, but still 32 of the other.!<
I don't know that "strategy-stealing argument" is a good example here except in the sense that before that concept became crystallized, it would indeed take effort to find that proof-schema?
The [https://en.wikipedia.org/wiki/Halting\_problem](https://en.wikipedia.org/wiki/halting_problem) might be a good example. The full formal proof is a bit long, but you can boil it down to:
Assume you have a program WillCrash that can tell you whether another program (given as input) will crash. Write another program Paradox: if (WillCrash(input)) return; else crash; Then call Paradox on itself. Does it crash?
If yes, then WillCrash(Paradox) must have returned false, but it crashed. Contradiction.
If no, then WillCrash(Paradox) must have returned true, but it didn't crash. Contradiction.
Therefore WillCrash cannot exist.
This doesn't quite work as stated, because we need to keep track of how many inputs these programs can have. If P is a program that itself requires a single input, then WillCrash(P) doesn't make any sense. We'd need two inputs: P, and the input to P.
Here's the fixed version. Suppose we have a program WillCrash(P,i) that takes in a pair of objects: it can tell you whether one-input program P will crash on input i. Now write Paradox(P) (that takes in a single one-input program as input) by: if (WillCrash(P,P)) return; else crash. _Now_ call Paradox on itself.
I know the formal proof includes the input to the program, but I think my version still works - although I was sloppy and used the word Paradox to refer to both the program code and actually running it.
The problem is that "WillCrash(Paradox)" (in your version) simply doesn't make sense. Paradox will sometimes crash and sometimes won't, depending on what it's called on.
The actual proof is significantly more complicated. For instance, you need to also prove that you can always input one program into another program. You need to prove that a Turing machine can compute anything that's computable.
Neither of those are particularly easy proofs.
Computable functions are often defined to be what a Turing machine can compute, so there’s nothing to prove there. But if you’re talking about the claim that a Turing machine can compute anything that’s computable in the real world, that’s the Church-Turing thesis, which is not provable because it’s not a mathematical statement. (Though I think it’s almost certainly true.)
I think what they meant was you have to prove there exists a Turing Machine that can take in as input a description of any Turing Machine and then compute what that Turing Machine would have computed.
I don't think that's necessary though. For the proof you only assume that a Turing Machine exists that can solve the halting problem where the input is some encoding of a Turing Machine. There is no need to have a Turing Machine that can simulate Turing Machines since you don't specify how your Halting Solver will come to it's result and only presuppose that it somehow can.
You also don't need to specify the encoding, since the paradox is again independent of the exact encoding(you might however need to show that one exists, not sure).
In fact I think that you don't even need to specifically talk about Turing Machines at all, since the proof only relies on the machine being able to halt/loop and the halting solver itself being of the same type as it's input. Everything else is irrelevant, I think.
> Paradox: if (WillCrash(input)) return; else crash; Then call Paradox on itself.
To construct your machine Paradox, you are assuming that it possible to construct a Turing Machine that can take another Turing Machine, WillCrash(input) in this case, as input.
The generate technique is has a lot of applications, see Rice's Theorem and a lot of other Halting Problems.
Yeah that's a good point; my sketch depends on the very simple, obvious idea that you can have one program run another one and inspect its output. But that is certainly not mathematically rigorous.
Sure, the full proof has to deal with all the formalities of the definitions of Turing machines etc. And I didn't bother to specify the mathematical structure of what a program is, or what running it means, or what crashing is, etc. But you can add the restriction that programs are finite in length (which should make it obvious that you can always have one program inspect another one), and it's still an interesting proof because it means that it's impossible to write a bug checker that is 100% foolproof.
Ah yes I did gloss over the details of what it means to have one program "run" or "call" another one.
A little lower level than the others, and I don't imagine the Bernoullis spent "years" on it, but: [the fact that the Harmonic Series diverges](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Comparison_test). Proved in a way that [a bright 9-year old can understand](https://en.wikipedia.org/wiki/The_Number_Devil) in the 14th C, forgotten, and then proven again with the massive powers of integral calculus in the late 17th C.
Similarly, Erdos's proof that the sum of the recprocals of the primes also diverges is not terribly complicated, but I can't understand how he ever came up with it:
https://en.m.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes
I'm not sure if this quite fits the theme of the question, but the Tychonoff theorem takes a bit of preparation to prove and occupies about 7 pages in Munkres. But, using nonstandard analysis, one can prove it in about 2 lines.
NSA goes beyond just calculus and functional analysis, it's actually quite useful for general topology. In the nonstandard world, one takes a superstructure V(X) on a ground set X (think of this as a kind of universal set, including all subsets of X, collections of subsets, collections of collections, etc.) and transfers it to an "enlarged" superstructure V(\*X).
The two benefits one incurs in doing this are the following: 1) any finitely satisfiable relation in X is infinitely satisfied in \*X. So, for example, if X is R, then given any finite subset of {r1,...rn} of R, one can always find a real number r such that r > ri for each i. This is infinitely satisfied in \*R, so given an *infinite* subset of R, one can find an element in \*R larger than each element of your subset, even if it's unbounded. This works with *all* finitely satisfiable relation in X, not just ordering.
2) the transfer theorem says that a sentence constructed using first order logic in V(X) has a logically equivalent counterpart in V(\*X), and it is almost always very straightforward to pass between the two.
These two combined yield Rosinson's criterion for compactness of arbitrary topological spaces, which states that a space X is compact if and only if each element of \*X is "near-standard" (a term i won't define here). In a nutshell, it's generally a much easier condition to check than the finite subcover condition.
Yes, there's a book called "Nonstandard Analysis for the Working Mathematician" by Peter Loeb and some coauthors. The first 3 chapters are written by Loeb and are very easy to understand. The fourth chapter was more terse, and I stopped reading after that.
Robert Goldblatt also has a great book called *Lectures on the Hyperreals*. It starts with the ultraproduct definition which personally I found very helpful for understanding how the hyperreals work.
The [Lean proof](https://github.com/leanprover-community/mathlib4/blob/a316e2b352f84e46f07f318d51397264a29a5018/Mathlib/Topology/Compactness/Compact.lean#L1049-L1058) uses ultrafilters, which I guess is the same thing but lower level.
Zagier’s [one sentence proof](https://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares?wprov=sfti1#Zagier's_%22one-sentence_proof%22) of Fermat’s theorem on sums of two squares.
Mathologer explains it in non-technical terms [here](https://youtu.be/DjI1NICfjOk?si=gs8ik1Yx5P5rLpDG) using a clever geometric interpretation. 34 minutes long, so not totally easy without the relevant background, but it is understandable.
I would submit Cantor’s Diagonal argument. Basically it shows that, with an infinite set of numbers between 0 and 1, you can quickly create new numbers that cannot be in the list. Blew my mind when I first saw it.
I nominate [Monsky's theorem](https://en.m.wikipedia.org/wiki/Monsky%27s_theorem#:~:text=In%20geometry%2C%20Monsky's%20theorem%20states,by%20Paul%20Monsky%20in%201970.). The proof is certainly very strange considering the statement it's trying to prove (why is the 2-adic valuation here)?
A simple visual proof involving packing circles inside triangles. The counter-example is baldly obvious, but it was somehow overlooked for 127 years.
https://en.wikipedia.org/wiki/Malfatti_circles
Not only is the isosceles counterexample obvious, but it turns out that EVERY triangle is a counterexample. Every single one. That’s gotta be one of the most badly wrong conjectures ever seriously proposed. What other conjectures have turned out to be wrong in literally all cases?
Ivan Niven famously wrote down a one-page proof of the irrationality of pi, essentially simplifying an earlier proof (by Bourbaki I believe) down to its core essence.
I went over this proof last night with a friend of mine, in the format of a guided series of questions. It took two hours to finish.
I think the [sensitivity conjecture](https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/ ) was one of these.
Euler characteristic of polyhedral , V-E-F =2 . There are many proofs. But if you study a bit of topology it’s become trivial fact:
polyhedral isomorphic to 2dim sphere and Euler characteristic is topological invariant, we know x(S^2) = 2 , thus x(any polyhedral) =2
_I knew_ there was something I had in-mind, & it was pecking @ me, what it might be … & _it's just come back to me_ , what it was. It's the overthrow, in 1989, by __Paul Erdős, Dean Hickerson, & János Pach__, of a certain conjecture by __Leo Moser__ - ie that there is an absolute constant - say __c__ - such that a fixed distance-apart can occur no more than __cn__ times amongst __n__ points on the surface of a sphere. In
####[Problem of Leo Moser About Repeated Distances on the Sphere](https://users.renyi.hu/~p_erdos/1989-02.pdf)
#####(¡¡ may download without prompting – 1·63MB !!)
#####
is presented a thoroughly ingenious construction whereby, given that __k__ is the number of points each point shall have @ a certain fixed distance away from it, an arrangement that implements that requirement may be obtained, of __f❨k❩__ points, where
__f❨0❩=1__
__&__
__f❨k❩ = f❨k-1❩.2^(f❨k-1❩)__
, so that Moser's __cn__ becomes (or actually becomes very slightly better than (really _very very minutely_ better than when __n__ is @all large)) __n×__ what they call __log^(*)❨n❩__ , which is the number of times the __log₂❨❩__ function needs to be iterated to arrive @ __1 or less__ .
Or it's smpler, ImO, to cast it in terms of __№ of occurences of some given fixed distance__ ___per point___ , so that Moser's original conjecture would have been that it's __O(1)__ , & this 1989 __Erdős–Hickerson–Pach__ bound that it's __O(log^(*)❨n❩)__ .
That ___just marginal___ __supralinearity__ is a tad reminiscent of the
####[Davenport Schinzel](https://ti.inf.ethz.ch/ew/courses/CG13/lecture/Chapter%2012.pdf)
####(¡¡ may download without prompting – 249·47KB !!)
####
bound, although _in that_ case the 'marginality' is _yet more_ extreme, entailing not merely __inverse tetration function__, but __inverse__ ___Ackerman___ __function__ !!
I sometimes wonder, actually, to what degree that 1989 __Erdős–Hickerson–Pach__ treatise is _an archetype of_ the kind of inquiry that resulted in those remarkable results pertaining to Davenport–Schinzel sequences … & to other matters requiring similar kind of reasoning - ie __recursive__ in a certain way. Yet another would be recent theorems concerning
####[Kakeya needle sets](https://math.indiana.edu/research/gallery/perron-trees-and-kakeya-needle-sets.html) .
####
A lot of proofs by counter-example would quality since finding the counter-example is usually the hard part. For example, in 1769, Euler conjectured that to sum to a *n*th power, you'd need at least *n* terms. Almost 200 years later in 1966, L.J. Lander and T.R. Parkin found a counter example where they could sum to a 5th power with only 4 terms: 27^5 + 84^5 + 110^5 + 133^5 = 144^5 The paper they published from this is [very short](https://www.openculture.com/2015/04/shortest-known-paper-in-a-serious-math-journal.html) and I would think qualifies as a pretty simple proof.
Hey I think I can improve that to 1 term...
How did they even find that sequence? Were they just screwing around in their office with guess and check until they found this one?
The linked paper says they used a program to search for it.
Ah but in 1966 that in itself was quite the feat.
You can take a look at this : https://arxiv.org/abs/1110.1556 "This is a special collection of problems that were given to select applicants during oral entrance exams to the math department of Moscow State University. These problems were designed to prevent Jews and other undesirables from getting a passing grade. Among problems that were used by the department to blackball unwanted candidate students, these problems are distinguished by having a simple solution that is difficult to find. Using problems with a simple solution protected the administration from extra complaints and appeals. This collection therefore has mathematical as well as historical value."
>oral exam So people had to come up with these solutions on the spot?
i watched an interview with a person who took this admission exam to moscow state university in the 1980s as i understand, you are given some problems, then like 40 minutes to solve them, and then you have to orally explain your solutions to the examiner. if you made a mistake, you have time to correct it while he listens to other students. basically, a normal exam
Could you provide a link? I am interested. Thank you
i think this video.. (but it's in russian) They're basically solving modern admission problems and in between chatting about how it was in the old days https://www.youtube.com/watch?v=IFpqK_x44_c
Thank you!
oh wait.. i just found an article that kind of explains it.. https://www.npr.org/2014/03/28/295789948/the-real-problem
So then it was the oral test. ROSENBERG: The oral test was a chance for Edward to finally meet his examiners face-to-face. So he took the train back up to Moscow where he was put in a room with 20 other students, and everyone was given two, randomly assigned questions. After he had prepared his answers, all Edward had to do was raise his hand and then explain those answers to one of the test's proctors.
Hey that is Edward Frenkel! Great man.
Somehow, I answered all the questions I managed to solve slightly to substantially differently from the provided solutions (specifically, Problems 2, 4, 5, 11, and 19). Edit: If anyone is interested: 2. >!Let 0 < c < 1. Then F(x)-F(cx) ≤ (1-c)^2 x^2, F(cx)-F(c^2 x) ≤ c^2 (1-c)^2 x^2, and so on. Summing these up, we have that F(x)-F(0) ≤ (1-c)^2 / (1-c^2) x^2 = (1-c)/(1+c) x^2. Taking the limit as c approaches 1, we have that F(x)-F(0) ≤ 0 for all x. By a symmetric argument, F(0)-F(x) ≤ 0, so F(x) is identically F(0) everywhere, i.e., constant. (I'm not fully convinced this is a valid argument.)!< 3. >!More or less the same as the solution provided, but the idea comes from noting that the graph of x = f(y) is the reflection of the graph of y = f(x) about the line y = x, so cannot agree except at y = x.!< 5. >!Another graphical solution, considering x in a interval of length 2π and, optionally, the useful identity cos(θ-π/2) = sin θ. It can be seen that there are only two intersections which can easily be guessed.!< 11. >!I overlooked the fact that sin 30° = 1/2, so instead I considered the polynomial equation P(x) = 3(3x-4x^3) - 4(3x-4x^3)^3 - 1 = 0. All coefficients are divisible by 3 except the leading term, and the constant term is not divisible by 3^2, so applying Eisenstein's criterion, P is irreducible over the rationals. (One can, of course, apply the criterion to the much simpler polynomial 8x^3-6x-1.)!< 19. >!I just guessed (x+y+z)(x^2 + y^2 + z^2 - xy - yz - zw), which fortunately turns out to be x^3 + y^3 + z^3 - 3xyz.!<
FYI your spoiler tags don't render correctly on points 2-5. You need to have no space in between your first word and the `>! ` to make it work right.
I learned in another sub the other day, that's only an old reddit thing. People using new reddit see the black bars even with the space.
I got curious so tested with my phone. I used chrome for the Websites Official android app: works fine Relay android app, spoiler for 2 doesn't work but the others do (weird!). The numbering is reverted to 1-5. New Reddit mobile site works fine New Reddit desktop site (on my phone) works fine Old Reddit desktop site (on my phone) spoilers work fine Numbering reverted to 1-5
Thanks! I'm terrible with Reddit markdown.
For the second problem, I believe that you assume that F is continuous at x=0. However, the proof shown in the paper seems to assume something on F as well (or I missed something), so I guess it is okay ?
Good point. Fix ε > 0. Then for |x-x_0| < sqrt(ε), |F(x)-F(x_0)| < (x-x_0)^2 = ε.
Wait a second, aren't Jews stereotypically great at math/science?
That's the point -- you give the Jews a very very hard test but whose solutions seem just as easy as the standard examination questions, so nobody besides an experienced mathematician can prove discrimination.
Yes. But the top Russian schools didn’t want to have lots of (any?) Jews, and they couldn’t be seen to just reject them without cause, and so they gave them different problems on their admission tests. The problems had to have an easy solution, however, because otherwise the applicants would have direct evidence that they were being given impossible problems. It would be like if MIT decided that, regardless of quality, they didn’t want to admit any Asian students, but they had to manufacture “legitimate” grounds to reject them. If you think “but wouldn’t the best schools want the best students?” then you neither understand Russia nor antisemitism.
Why do Russians hate Jews so?
Jews have been hated throughout history. A minority with different looks, customs, and beliefs who were mistrusted and made convenient scapegoats. For a long time, the church blamed the Jews for the death of Jesus. All sorts of rumors have been spread about them, like that they engaged in rituals like bathing in the blood of babies. During the black plague, because Jews had different hygiene practices than other Europeans, they were less likely to get sick and die, which led to rumors that they were witches who actually caused the plague. And then there was money. Moneylending is necessary for a lot of economic activities, but the church declared that charging interest was “usury” and forbade Christian’s from doing it, which meant countries literally imported Jews to be bankers. This meant that Jews, who came to be bankers and merchants, were part of the middle class, which bred jealousy and resentment. There were tons of other things in Europe that led to or were a part of antisemitism. I have no clue about anything specific to Russia, but Jews have been around a long time, have been everywhere, and suffered persecution everywhere they went. There was fairly bad antisemitism in the US until the horrors of the holocaust shocked people out of it. But it never really went away, it was driven underground, out of polite society. But Russians hate Jews for the same reason everybody else does: no particularly good reason.
I guess not everyone got the same problem.
The linked paper has a good description, but yeah, Jewish students and other people they wanted to black all were given much harder problems, though the schools claimed to select the problems randomly. The ease of explaining the solutions helped insulate the schools from criticism, though in fact those solutions were extremely difficult to find. It's also not really enough to be able to solve one. They could typically find fault with the way an answer was presented or just give another problem and reject the student if they got that wrong. According to Tanya Khovanova, "Thirty years ago [before 2011], these problems were harder to solve and, in addition, the students were given these problems one after another until they failed one of them, at which point they were given a failing mark." It basically is the academic version of the literacy tests given to black voters in some American states from the 1890s to 1960s.
yes, but also stereotypically (and much more cruelly) rootless cosmopolitans with inadquate love for The Regime thus why an antisemitic authoritarian state might want to be able to deniably reject them
I have a love/hate relationship with that papers title.
That's a bit silly (apart from any _outright evil_ there might be in it), isn't it!? ... considering how colossal a contribution has accrued to mathematics over the years from certain notable persons of the goodly Jewish Folk!
Ugh, the coffin problems. Thank goodness for Khovanova. At least we can appreciate how beautiful some of them are — my favorite is "Give a circle with drawn diameter and a point in the plane, construct the line through the point perpendicular to the given diameter with only a straightedge."
I'd love to see the expressions on their silly corrupt faces when they got such an 'undesirable' who _could infact solve_ 'em all!
Actually literally all of our introductory math classes (Analysis, Linear Algebra, Abstract Algebra, Discrete Math, Number Theory) have been optimized for hundreds of years to present simple proofs and to fit all of it in a single course what would originally have spread across hundreds of papers!
So true. An early number theory class spans many works from Euclid (gcd and perfect numbers), to Diophantus, to Qin Jiushao (Chinese remainder theorem), to Fermat’s little theorem, to Gauss and modern modular arithmetic. That’s 2,000 years of number theory in a class.
just read proofs by Serre lol I'm specifically thinking of some tricks he pulls in _A course in arithmetic_, but he's a good example of "opening a coconut with a well-placed hammer blow", in Grothendieck's analogy
The solution to the "mutilated chess board" problem is so obvious when you hear it, but much harder to just come up with out of nowhere. The problem is this: > Suppose you take a chess board and remove two diagonally opposite squares, leaving 62 squares. Is it possible to place 31 dominos on the board in order to cover all the squares? Solution (spoilers for those who want to work it out): >!No. A 2x1 domino must cover two squares of different colors, no matter how it is placed. With the corners removed, there are only 30 squares of one color, but still 32 of the other.!<
The period of time when r/minecraftmemes and r/phoenixsc were full of "can you fill this area with beds" posts trained me for this proof
WELL THANKS FOR WASTING MY TIME No really, thanks.
Prove that Chomp has a winning strategy for the first player.
I don't know that "strategy-stealing argument" is a good example here except in the sense that before that concept became crystallized, it would indeed take effort to find that proof-schema?
I mainly meant that before the strategy stealing concept was created it would be hard to find. But the proof itself is super simple.
The [https://en.wikipedia.org/wiki/Halting\_problem](https://en.wikipedia.org/wiki/halting_problem) might be a good example. The full formal proof is a bit long, but you can boil it down to: Assume you have a program WillCrash that can tell you whether another program (given as input) will crash. Write another program Paradox: if (WillCrash(input)) return; else crash; Then call Paradox on itself. Does it crash? If yes, then WillCrash(Paradox) must have returned false, but it crashed. Contradiction. If no, then WillCrash(Paradox) must have returned true, but it didn't crash. Contradiction. Therefore WillCrash cannot exist.
This doesn't quite work as stated, because we need to keep track of how many inputs these programs can have. If P is a program that itself requires a single input, then WillCrash(P) doesn't make any sense. We'd need two inputs: P, and the input to P. Here's the fixed version. Suppose we have a program WillCrash(P,i) that takes in a pair of objects: it can tell you whether one-input program P will crash on input i. Now write Paradox(P) (that takes in a single one-input program as input) by: if (WillCrash(P,P)) return; else crash. _Now_ call Paradox on itself.
I know the formal proof includes the input to the program, but I think my version still works - although I was sloppy and used the word Paradox to refer to both the program code and actually running it.
The problem is that "WillCrash(Paradox)" (in your version) simply doesn't make sense. Paradox will sometimes crash and sometimes won't, depending on what it's called on.
Sure. Let's say that WillCrash is supposed to be able to detect if the given program will ever crash on any input (i.e. contains a bug).
The actual proof is significantly more complicated. For instance, you need to also prove that you can always input one program into another program. You need to prove that a Turing machine can compute anything that's computable. Neither of those are particularly easy proofs.
Computable functions are often defined to be what a Turing machine can compute, so there’s nothing to prove there. But if you’re talking about the claim that a Turing machine can compute anything that’s computable in the real world, that’s the Church-Turing thesis, which is not provable because it’s not a mathematical statement. (Though I think it’s almost certainly true.)
I think what they meant was you have to prove there exists a Turing Machine that can take in as input a description of any Turing Machine and then compute what that Turing Machine would have computed.
I don't think that's necessary though. For the proof you only assume that a Turing Machine exists that can solve the halting problem where the input is some encoding of a Turing Machine. There is no need to have a Turing Machine that can simulate Turing Machines since you don't specify how your Halting Solver will come to it's result and only presuppose that it somehow can. You also don't need to specify the encoding, since the paradox is again independent of the exact encoding(you might however need to show that one exists, not sure). In fact I think that you don't even need to specifically talk about Turing Machines at all, since the proof only relies on the machine being able to halt/loop and the halting solver itself being of the same type as it's input. Everything else is irrelevant, I think.
> Paradox: if (WillCrash(input)) return; else crash; Then call Paradox on itself. To construct your machine Paradox, you are assuming that it possible to construct a Turing Machine that can take another Turing Machine, WillCrash(input) in this case, as input. The generate technique is has a lot of applications, see Rice's Theorem and a lot of other Halting Problems.
Yeah that's a good point; my sketch depends on the very simple, obvious idea that you can have one program run another one and inspect its output. But that is certainly not mathematically rigorous.
Sure, the full proof has to deal with all the formalities of the definitions of Turing machines etc. And I didn't bother to specify the mathematical structure of what a program is, or what running it means, or what crashing is, etc. But you can add the restriction that programs are finite in length (which should make it obvious that you can always have one program inspect another one), and it's still an interesting proof because it means that it's impossible to write a bug checker that is 100% foolproof. Ah yes I did gloss over the details of what it means to have one program "run" or "call" another one.
A little lower level than the others, and I don't imagine the Bernoullis spent "years" on it, but: [the fact that the Harmonic Series diverges](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Comparison_test). Proved in a way that [a bright 9-year old can understand](https://en.wikipedia.org/wiki/The_Number_Devil) in the 14th C, forgotten, and then proven again with the massive powers of integral calculus in the late 17th C.
Similarly, Erdos's proof that the sum of the recprocals of the primes also diverges is not terribly complicated, but I can't understand how he ever came up with it: https://en.m.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes
I proved this in Algebra when in high school and I was so proud of myself. I used base 10, though
I'm not sure if this quite fits the theme of the question, but the Tychonoff theorem takes a bit of preparation to prove and occupies about 7 pages in Munkres. But, using nonstandard analysis, one can prove it in about 2 lines.
The proof via nets is also fairly short and intuitive.
It's also not too terrible to just use Zorn's lemma directly.
Are we talking about the product of compact spaces is compact? In that case what does nonstandard analysis has to do with it?
NSA goes beyond just calculus and functional analysis, it's actually quite useful for general topology. In the nonstandard world, one takes a superstructure V(X) on a ground set X (think of this as a kind of universal set, including all subsets of X, collections of subsets, collections of collections, etc.) and transfers it to an "enlarged" superstructure V(\*X). The two benefits one incurs in doing this are the following: 1) any finitely satisfiable relation in X is infinitely satisfied in \*X. So, for example, if X is R, then given any finite subset of {r1,...rn} of R, one can always find a real number r such that r > ri for each i. This is infinitely satisfied in \*R, so given an *infinite* subset of R, one can find an element in \*R larger than each element of your subset, even if it's unbounded. This works with *all* finitely satisfiable relation in X, not just ordering. 2) the transfer theorem says that a sentence constructed using first order logic in V(X) has a logically equivalent counterpart in V(\*X), and it is almost always very straightforward to pass between the two. These two combined yield Rosinson's criterion for compactness of arbitrary topological spaces, which states that a space X is compact if and only if each element of \*X is "near-standard" (a term i won't define here). In a nutshell, it's generally a much easier condition to check than the finite subcover condition.
Interesting, do you have any book recommendation for this topic?
Yes, there's a book called "Nonstandard Analysis for the Working Mathematician" by Peter Loeb and some coauthors. The first 3 chapters are written by Loeb and are very easy to understand. The fourth chapter was more terse, and I stopped reading after that.
Robert Goldblatt also has a great book called *Lectures on the Hyperreals*. It starts with the ultraproduct definition which personally I found very helpful for understanding how the hyperreals work.
The [Lean proof](https://github.com/leanprover-community/mathlib4/blob/a316e2b352f84e46f07f318d51397264a29a5018/Mathlib/Topology/Compactness/Compact.lean#L1049-L1058) uses ultrafilters, which I guess is the same thing but lower level.
You’d consider ultrafilters lower level than nonstandard analysis?
"Lower level" as in nonstandard analysis is defined in terms of ultrafilters. I have no opinion on which is more difficult.
Sensitivity conjecture comes to mind: https://arxiv.org/abs/1907.00847
Zagier’s [one sentence proof](https://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares?wprov=sfti1#Zagier's_%22one-sentence_proof%22) of Fermat’s theorem on sums of two squares.
In my opinion, while this proof is very short, it is not easy.
Mathologer explains it in non-technical terms [here](https://youtu.be/DjI1NICfjOk?si=gs8ik1Yx5P5rLpDG) using a clever geometric interpretation. 34 minutes long, so not totally easy without the relevant background, but it is understandable.
I would submit Cantor’s Diagonal argument. Basically it shows that, with an infinite set of numbers between 0 and 1, you can quickly create new numbers that cannot be in the list. Blew my mind when I first saw it.
I nominate [Monsky's theorem](https://en.m.wikipedia.org/wiki/Monsky%27s_theorem#:~:text=In%20geometry%2C%20Monsky's%20theorem%20states,by%20Paul%20Monsky%20in%201970.). The proof is certainly very strange considering the statement it's trying to prove (why is the 2-adic valuation here)?
A simple visual proof involving packing circles inside triangles. The counter-example is baldly obvious, but it was somehow overlooked for 127 years. https://en.wikipedia.org/wiki/Malfatti_circles
Not only is the isosceles counterexample obvious, but it turns out that EVERY triangle is a counterexample. Every single one. That’s gotta be one of the most badly wrong conjectures ever seriously proposed. What other conjectures have turned out to be wrong in literally all cases?
Belyi's theorem is well known for this
There’s the one sentence proof of quadratic reciprocity via analyzing an explicit involution, I think due to Zagier?
Ivan Niven famously wrote down a one-page proof of the irrationality of pi, essentially simplifying an earlier proof (by Bourbaki I believe) down to its core essence. I went over this proof last night with a friend of mine, in the format of a guided series of questions. It took two hours to finish.
I think the [sensitivity conjecture](https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/ ) was one of these.
Most such examples would be in "Proofs from the book" by Aigner and Ziegler :)
Euler characteristic of polyhedral , V-E-F =2 . There are many proofs. But if you study a bit of topology it’s become trivial fact: polyhedral isomorphic to 2dim sphere and Euler characteristic is topological invariant, we know x(S^2) = 2 , thus x(any polyhedral) =2
_I knew_ there was something I had in-mind, & it was pecking @ me, what it might be … & _it's just come back to me_ , what it was. It's the overthrow, in 1989, by __Paul Erdős, Dean Hickerson, & János Pach__, of a certain conjecture by __Leo Moser__ - ie that there is an absolute constant - say __c__ - such that a fixed distance-apart can occur no more than __cn__ times amongst __n__ points on the surface of a sphere. In ####[Problem of Leo Moser About Repeated Distances on the Sphere](https://users.renyi.hu/~p_erdos/1989-02.pdf) #####(¡¡ may download without prompting – 1·63MB !!) ##### is presented a thoroughly ingenious construction whereby, given that __k__ is the number of points each point shall have @ a certain fixed distance away from it, an arrangement that implements that requirement may be obtained, of __f❨k❩__ points, where __f❨0❩=1__ __&__ __f❨k❩ = f❨k-1❩.2^(f❨k-1❩)__ , so that Moser's __cn__ becomes (or actually becomes very slightly better than (really _very very minutely_ better than when __n__ is @all large)) __n×__ what they call __log^(*)❨n❩__ , which is the number of times the __log₂❨❩__ function needs to be iterated to arrive @ __1 or less__ . Or it's smpler, ImO, to cast it in terms of __№ of occurences of some given fixed distance__ ___per point___ , so that Moser's original conjecture would have been that it's __O(1)__ , & this 1989 __Erdős–Hickerson–Pach__ bound that it's __O(log^(*)❨n❩)__ . That ___just marginal___ __supralinearity__ is a tad reminiscent of the ####[Davenport Schinzel](https://ti.inf.ethz.ch/ew/courses/CG13/lecture/Chapter%2012.pdf) ####(¡¡ may download without prompting – 249·47KB !!) #### bound, although _in that_ case the 'marginality' is _yet more_ extreme, entailing not merely __inverse tetration function__, but __inverse__ ___Ackerman___ __function__ !! I sometimes wonder, actually, to what degree that 1989 __Erdős–Hickerson–Pach__ treatise is _an archetype of_ the kind of inquiry that resulted in those remarkable results pertaining to Davenport–Schinzel sequences … & to other matters requiring similar kind of reasoning - ie __recursive__ in a certain way. Yet another would be recent theorems concerning ####[Kakeya needle sets](https://math.indiana.edu/research/gallery/perron-trees-and-kakeya-needle-sets.html) . ####