Live data from Hacker News

The emoji problem (2022)

artofproblemsolving.com

11–20 of 71 posts

Re: The emoji problem (2022)

#11
The theory of elliptic curves goes amazingly deep. Scratching the surface slightly more, to fill in the article's "ignore the labels like 2P":

Intersecting the curve with lines the way the author does is, perhaps shockingly, a commutative group operation, known as point addition. You define this operation by saying that the three points A,B,C on a line sum to zero: that is A+B+C=0 or in other words, A+B = -C. Reflecting across the curve's line of symmetry is negation (there's an alternative definition that extends to curves without reflection symmetry). Combining the two defines an operation A+B which adds two points on the curve and gives a third one: draw the line from A to B, intersect it with the curve to find a point -A-B (using the same type of formula given in this article) and then reflect it to get A+B. This addition operation obviously commutes (meaning, the line between A and B is the same as the line between B and A), but surprisingly it also associates and you get a group operation.

(For math olympiad nerds out there: so the union of a conic and a line is also a bivariate cubic equation. You can carry out the same "addition" operation there. Again the operation clearly commutes. But it also associates! This is basically Pascal's theorem.)

The theory of elliptic curves is also the basis of elliptic curve cryptography. In that case, instead of the curve being over the reals, all the calculations are done mod some prime p, which destroys structure based on continuity and prevents the numbers from becoming too large. There are a bunch of subtleties here but the key is that you can still straightforwardly compute addition in this context, with basically the same formulas. Then from addition you can get n*A, both for small integers n (eg 5*A = A+A+A+A+A) but also for large n (e.g. 2*A = A+A; 66*A = 2*2*2*2*2*2*A + 2*A). This "scalar multiplication" operation is a one-way operation for appropriately chosen curves: it's easy to calculate n*A from (n,A), but as far as we know it is hard to calculate n from (A,n*A) ... at least if you can't build a large quantum computer.

This gives you mix of easy operations (eg, addition and scalar multiplication) plus problems believed to be hard, which is a great starting point to build cryptography. There are a lot of important technical details, though fewer than with the new lattice schemes.

(Further comment on the olympiad thing: so you can do this with conic+line too, extending from addition to multiplication and using the same formulas mod p. But it's not as good: it's not hard to find a projection that sends the line to infinity and the conic to the unit circle or similar, and then the group operation becomes equivalent to multiplying the points' coordinates as complex numbers or similar. If the group operation is equivalent to multiplication, then scalarmul becomes equivalent to exponentiation, which ends up being in Fp or Fp^2 depending on some Legendre symbol or other. Exponentiation is still potentially secure: it's basically classical Diffie-Hellman. However, more attacks are known on exponentiation in Fp or Fp^2: the attacks don't outright break it but you need p to be much bigger.)

Edit: unescaped stars make italics.

Re: The emoji problem (2022)

#12
post #3

Once upon a time I was good at math -- like, win state-wide competitions, get a scholarship good. It's sad that I can easily follow the path laid out here, but I am nowhere close to being able to lay out this course on my own.

[deleted]

Re: The emoji problem (2022)

#14
post #7
post #6

Earlier quoted context omitted.

Nobody can do this on their own. You don't get to do this by having a great aptitude for high school maths and then being exposed to one or two more concepts that just intuitively click - which is enough to be competitive at the level you describe, though not enough to make the US Olympiad team. You get the level of understanding necessary to create this blog post by already having worked through several textbooks an…

you seem to be missing this idea that mathematics must be doable alone, individually this appears to be what sets mathematics appart from science? I mean, it's not like Euler, or Poincaré, and so on, are really there with you when "doing math" point being, mathematics is not a team game. but everything else is??

When I'm teaching congruence or the Gauss method to solve equation systems, I tell my students: "You can solve the midterm alone or with the ghost of Gauss sit on the side chair."

Re: The emoji problem (2022)

#16
post #6
post #3

Once upon a time I was good at math -- like, win state-wide competitions, get a scholarship good. It's sad that I can easily follow the path laid out here, but I am nowhere close to being able to lay out this course on my own.

Nobody can do this on their own. You don't get to do this by having a great aptitude for high school maths and then being exposed to one or two more concepts that just intuitively click - which is enough to be competitive at the level you describe, though not enough to make the US Olympiad team. You get the level of understanding necessary to create this blog post by already having worked through several textbooks an…

The picture says 95% are unable to solve this - I wonder what the correct percentage is. Closer to 99.999% I would guess, based on your explanation.

Re: The emoji problem (2022)

#18

I love this genre! I've started calling it “Dantzig Sniping” and here’s my own one: https://x.com/TheOisinMoran/status/1298305686082744320 Some more context and related ones here: https://x.com/TheOisinMoran/status/1299124512240398336

I thought you named it for Gdańsk (Danzig) and was wondering what’s got sniped there :)

Re: The emoji problem (2022)

#19
post #8
post #7

Earlier quoted context omitted.

you seem to be missing this idea that mathematics must be doable alone, individually this appears to be what sets mathematics appart from science? I mean, it's not like Euler, or Poincaré, and so on, are really there with you when "doing math" point being, mathematics is not a team game. but everything else is??

> point being, mathematics is not a team game. but everything else is?? Sorry, it’s early, and I can’t tell if you’re being sarcastic. I hope you are? Mathematics is very much a team game.

i think based on the username they seem to be looking for validation through upvotes. Perhaps assuming this place is like a nerdier reddit.
Post reply on HN