For anyone looking to learn more about elliptic curves, which are astoundingly "well-connected" as math topics go, here's a good book that should be accessible to anyone with some calculus under their belt:
So what do I mean by "well-connected"? Elliptic curves are associated with
a) number theory - many questions about number theory boil down to finding points on elliptic curves with rational coordinates
b) algebraic geometry - elliptic curves are very "nice" from this point of view, and they are complicated enough that you can say interesting things, but not so complicated that you can't say anything
c) complex analysis - over the complex plane, an elliptic curve is a torus. You might have seen how a torus can be formed by identifying opposite edges of a square, and an elliptic curve is hence "a quotient of C by a square lattice". Modular forms, which are creatures of complex analysis with deep applications to number theory, are naturally defined in this framework.
and many more things I don't know about. They're in a sort of "sweet spot" and act as a bridge between multiple parts of mathematics.
I tried to crack this problem, and ended up (very naively) resorting to substituting division with modulo operation that is, a%(b+c) + b%(a+c) + c%(a+b) = 4 of which the min solution is a=1, b=2, and c=4. I am glad that the true solution involved EC which, if my understanding is correct, is basically modular operations in high-dimensional space.
Elliptic curves are "generalized modular arithmetic" only in the sense that they involve a different kind of addition law (the set of points on a nice EC is a group).
Also, you can look at the points on an elliptic curve where you allow the coordinates to be real, complex, rational, or even the integers mod p (any field will do), so the last choice gives you a closer link with modular arithmetic. It's best to treat ECs as their own weird, wonderful beasts!
This is a great article. Little puzzles like these are often the gateways to enormous mathematical journeys. Here, I only wished the journey was more detailed -- you could motivate all of these operations -- but that would take many pages.
Really? The math content on Quora is generally top notch. It depends on who answers the question of course, but there are many high quality writers on Quora with deep understandings of mathematics.
Agreed. Besides HN, and Reddit for occasionally indulging my darker political side, Quora is the only social content I regularly consume. Besides math, there's also some excellent writers on machine learning and computer science.
How does Quora works? I regularly see very interesting answers there. While it looks like SO clone, its content is different. Do they pay for good answers? Or they just happen to have bright people in their community?
I initially tried that on WolframAlpha but it doesn't understand Mathematica syntax. But one can enter it on https://lab.wolframcloud.com after creating an account.
Just for fun, what if it is read as AND: that is, bitwise AND?
x/(y&z) & y/(x&z) & z/(x&y) = 4.
If the / becomes integer (flooring) division, there are many solutions, such as (6, 13, 19).
But if the division results are required to actually be integers, there are no small solutions - at least, none where x, y, and z <= 10000 (checked by brute force with minor optimization). I suspect that unlike the original problem, there are actually no solutions, but it’s just a guess. Anyone want to come up with a proof? :)
It might be fun and surprising to come up with seemingly unsolveable problems in math, but it isn't actually that hard. Especially if you come from the angle of computer science. Math does not have common tools I'm aware of to deal with many of those problems.
Bitwise AND is not a linear function, which is a first obstacle.
For bitwise and you have to be solving it in a Galois field (And consider what AND does) which is actually easier than the general solution but points you more accurately at the cryptographic origin of the question.
We started stripping out a bunch of character ranges a few years ago because people were using them to play Unicode games in HN titles and the idea here is plain text. But I'm not sure in that case. You could test it if you wanted.
I tried it and it works. U+FF0B gives a plus sign when used in an HN title. It's a fair bit wider than normal, so may look a little off but not as off as "and". Here's a line of 10 U+FF0B's and a line of 10 +'s for comparison:
> Next up: what is the degree of our equation? The degree is the highest power of any term showing up. For example, if you have (a^2)b(c^4), that’s a term of degree 7 = 2 + 1 + 4
I thought that equation was degree 4, which aligns with what the author says later on. Am I missing something? It seems odd that he would write out that equation accidentally, maybe just crossed wires though. I'm sure we've all been there.
The wording in that paragraph is a bit confusing. In this context, "term" refers to the entire product, For example, the equation "(a^2)b + (b)c^4 = 0" has two terms: (a^2)b, and (b)c^4.
The degree of the entire equation is the maximum of the degree of the individual terms. However, the degree of a term is the sum of the degree of all of the factors.
For example, the equation "a+b+c=10" is degree 1, but "abc=10" is degree 3.
Ah ok so he was talking about the degree of the equation but gave an example of calculating the degree of a term, the highest of which in any equation is its degree. That makes sense, thanks for clearing it up!
The author defined degree poorly. a monomial x0^e0x1^e1...xn^en has degree e1+e2+...+en. A polynomial's degree is the highest degree of any of it's monomials.
Degree has the property that Deg(P1P2)=Deg(P1)Deg(P2)
If I understood your question correctly, you are saying that the degree of a term should be the maximum degree between the vatiables in that term. So (a^2)(b^1)(c^4) ) would be of degree max(2,1,4) = 4.
But with the definition he is using, the degree of a term in the equation is the sum of the degrees of the variables. So (a^2)(b^1)(c^4) has degree 2 + 1 + 4 = 7.
I don't think that's right. See the sibling comment, which made it click for me. He is saying the degree of a single term is the sum of the exponents in that term, and the degree of the equation is max(...all term degrees).
Let s(n) be the sum of all positive divisors of n. E.g., s(2) = 1 + 2, s(4) = 1 + 2 + 4, s(20) = 1 + 2 + 4 + 5 + 10 + 20.
Let H(n) = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n.
Question: is it true that s(n) < H(n) + log(H(n)) exp(H(n)) for all n > 1?
(log is natural logarithm)
It turns out that this simple looking problem is equivalent to the Riemann Hypothesis, which is perhaps the most important unsolved problem in pure mathematics. Many of the best minds in mathematics have attempted it in the approximately 160 years since Riemann posed it.
What equivalent means in this context is that if the Riemann Hypothesis is true, than the inequality above is also true, and if the inequality above is true, then the Riemann hypothesis is true.
Maybe just me, but that problem does not look very simple at all. One reason OP's problem is appealing, is because the solution can be easily checked. The solution is a kind of "proof of work". You could never guess the solution without a deep understanding of the problem. But once found, the solution is immediately verifiable.
For many problems one can easily guess the solution, without necessarily knowing the proof (like Fermat did). The answer is almost certainly negative, and a complete solution requires a very long and tedious proof that cannot be checked without a deep understanding of the field and many years of collective effort.
I am specifically interested in problems which can be understood by a child, have hard solutions which cannot be easily guessed, but are easily verified (ex. factoring the product of two large primes). It seems like these problems would make good candidates for one-way-functions, like the diophantine equations and ECC. But elliptic curve cryptology is too difficult to describe to a child.
Quite easy to explain given a few graphs. The explanation boils down on how hard is to accurately draw a curve of such an elliptic function at big x (P3) and then figure out which two other points intersect with a given line near. You can even show it on a big whiteboard.
You can even show how easy out would be for a simple curve where the left part is an easy equation.
The hard part is what makes an equation easy to solve. (And how some elliptic are broken.) It takes at least some high school math to hint at this.
Speaking of divisors, there are infinite numbers n such that n and n+1 have the same number of divisors. AFAIK we do not have a way to find such an n > N for any given N without calculating an infinitely growing sequence.
Is there a number which can be written in base 2,3,4,5,6 using only 0 and 1?
What's mind blowing here is that if you ask for base 2, 3, 4 the answers are trivial but for bases 2,3,4,5 somehow you get 82000 and we do not know whether there is another and for 6 it's unknown.
In general, number theory is notorious for containing many questions that are accessible to a layperson but whose proofs rely on arguments that are so difficult that even the basic idea of how the argument works takes many years of study.
Fermat's last theorem is an example, because it can be shown to be equivalent to, among other things, a very deep statement about elliptic curves (yep, the same thing The Fine Answer is about!) that Andrew Wiles proved.
From the past, we had Fermat's Last Theorem. Looking for ones that are not solved yet? How about "Collatz conjecture
"? I think there are more complex ones, but yeah, not so simple to explain.
from everything I've read, collatz has not merely resisted proof, but anything resembling progress. Erdos said that mathematics is not yet ready for such problems.
Conway showed that the generalized Collatz conjecture (recurrences with arbitrary cases dependent on the modulus) is computationally undecidable (halting problem reduces to it). The choice of modulus doesn't even need to be that big to get this result, only ~6500 or so. As far as I know, this is the only substantial result in either direction for this problem.
I suspect it is due to the lack of application for the solution.
I analyzed the problem for a while and theorized ways to collaboratively contribute to the solution. I settled on submitting an integer sequence to OEIS.
True. And there could be many more ridiculously simple problems with hard or no applications (at least for now) we may not be able to solve or progress at all. Math as we know and practice might still fall short. I, for one, be happy that simple to state but solved, Godel's Incompleteness theorem, about the imperfection of the tools, had set the things firmly on stone.
Solving them or progress? May be I don't care, but these little problem, simple ones does encourage one to start thinking about solving problems, they make math accessible to masses.
My favorite example are a few simple-seeming polynomials with integer solutions. (Equations that we want to solve for integers are called "Diophantene equations".)
Here's one that's genuinely easy:
x^3 + y^3 + z^3 = 29
The solution is x = 1, y = 1, z = 3 (or any permutation thereof).
So how about this one?
x^3 + y^3 + z^3 = 30
Play around a bit.
Not so easy.
But it does have a solution!
Here it is:
x = -283059965
y = -2218888517
z = 2220422932
And what about x^3 + y^3 + z^3 = 33? There is no known solution. It's an open problem!
This is a great visceral demonstration that Diophantene equations are hard: there can exist no algorithm that solves all of them. Diophantene equations, like the Halting Problem, are undecidable.
I was replying that the constants in question include 33, 42 and 74... and realized that I'm late :-) In a more recent survey, though, it is now known that:
On an infinite square grid where lines are 1 unit apart, if a circle of radius "r" is centered on an intersection, how many intersections lie within the circle? Answer in terms of "r".
Agree, good article. Thanks to it I think I understand more why cryptography based on elliptic curves (like Curve25519) is considered pretty safe for now.
They need to all be positive. FTA (on the solution x = 4, y = -1, y = 11) :
> This solution is not easy to see by hand, but it’s also not hard to discover with some patience without all the machinery we are reviewing here. It’s the positive solutions that are the lair of dragons.
A bit tangential but I wonder if something like that could relate to the slightly odd collection of fundamental particles we find in physics. They have properties that have to come out integral like spin x 2 and charge x 3 and have odd values like muons and tao particle being basically electrons but approx 200 and 3500 times heavier.
Yes. You can try the following smt2 script with yices2 [0]:
(set-logic QF_UFNIA)
(declare-fun x () Int)
(declare-fun y () Int)
(declare-fun z () Int)
(define-fun left-side () Int
(+ (+
(* (* x (+ x z)) (+ x y))
(* (* y (+ y z)) (+ x y)))
(* (* z (+ y z)) (+ x z)))
)
(define-fun right-side () Int
(* (* (*
4
(+ y z))
(+ x z))
(+ x y))
)
; disallow division by zero
(assert (not (= 0 (+ y z))))
(assert (not (= 0 (+ x z))))
(assert (not (= 0 (+ x y))))
(assert (= left-side right-side))
(check-sat)
(get-model)
Anything is possible, but I really doubt you'll find those 80 digit numbers. Maybe the sat solver includes some serious number theory though. I doubt it.
Does the `Int` datatype allow negative integers or is it non-negative only? This problem gets much more difficult if you restrict it to positive solutions only.
I once saw a youtube video which said that an object moving at 4m/s would be slowed down by [thing] by 0.00006m/s, so its new velocity would be 3.99994m/s
... except that no, its new velocity would be 4m/s. The author, a physicist, ignored sig figs. 4 - 0.00006 = 4, when you're dealing with measurements :)
'Uncertainty' is a much more ambiguous term that means many more things than 'imprecision of measurement'.
Still, I'm interested to hear why you think sig figs are high-school only when they're the standard way of writing in scientific notation. Do you genuinely think that the example I gave from the video is reasonable? It sounds like you're a theorist and have no experience in real-world application.
I realize when you say "isn't quite 4" you mean the solution is not quite equal to 4, but it could also be incorrectly interpreted as a solution that is slightly less than 4.
https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number...
It's not a textbook, which is both good and bad. In my case, it did a good job whetting my appetite for more!
A really well-written and not-extremely-difficult undergrad textbook on elliptic curves:
https://www.amazon.com/Rational-Points-Elliptic-Undergraduat...
(Non-affiliate links, just so you know.)