akalin

You might be interested in https://www.akalin.com/intro-erasure-codes , where I explain how to implement Reed-Solomon erasure codes.

I don't have a complete answer, but a first step would be to think of the coordinate-free concept behind transposes, which is the adjoint: https://en.wikipedia.org/wiki/Transpose#Adjoint

I agree re. being disguised by complicated math. Although even if you think it's elementary, I encourage you to write it up somewhere, like a blog post. I'm sure there are people out there like me who would find it novel. :)

If I ever do use it or write about it, I'll make sure to cite you. Thanks again!

No problem. Do you happen to have a source for the algorithm you explained, though? I recognize the parity-check matrix, but the rest I can't seem to find in any of the usual coding theory texts; usually, they treat erasures as part of the full RS decoding process.

You still mention that:

> There's no slick trick to check fast enough, whether or not a large number is prime. So much so that finding large prime numbers has been an obsession for mathematicians.

But that's still false; in fact, the rest of your article talks about the Fermat and Miller-Rabin primality test, which are indeed slick tricks that can check fast enough whether or not a large number is prime (to whatever degree of confidence you desire)!

Also, finding large prime numbers isn't really an obsession anymore -- you can use any of the fast primality test algorithms mentioned above, randomly generate numbers of a desired bit length, and stop when you hit a (probable) prime, which happens fairly quickly by the prime number theorem: https://en.wikipedia.org/wiki/Prime_number_theorem

You may be thinking of the search for Mersenne primes, or other primes of a specific form.

Ah, okay thanks. My coding theory is a bit weak, but it looks like this algorithm depends on the specific form of RS codes that you mentioned. I think the presentation outlines a form of RS erasure codes which is more general (e.g., allows Cauchy parity matrices instead of Vandermonde-derived ones).

Using a general matrix inversion is indeed inefficient, and becomes impractical for large k. However, the special-purpose row reduction algorithm I mentioned gets to O(nm^2) which is much better, although worse than the O(nm) algorithm you mentioned, which makes sense given that that one handles more specific RS codes.

Thanks for elaborating! It's reminding me that I really should brush up on coding theory, though -- do you have any resources/textbooks you'd recommend for someone familiar with the mathematical background? (Finite fields, etc.)

Can you elaborate more on the computation of the decoding matrix? Is it basically a special-purpose row reduction, taking advantage of the fact that the matrix to be inverted has a bunch of rows from the identity matrix? (I think it is, but would be curious if there's another algorithm out there!)

If you enjoy the discussion of permutations and cycles in this article, there's a puzzle you might also like:

Prisoner A is brought into the warden’s room and shown a faceup deck of 52 cards, lined up in a row in arbitrary order. She is required to interchange two cards, after which she leaves the room. The cards are then turned face down, in place. Prisoner B is brought into the room. The warden thinks of a card, and then tells it to B (for example, “the three of clubs”).

Prisoner B then turns over 26 cards, one at a time. If the named card is among those turned over, the prisoners are freed immediately. Find a strategy that guarantees that the prisoners succeed. (If they fail, they must spend the rest of their lives in prison.)

Needless to say: The two prisoners have the game described to them the day before and are allowed to have a strategy session; absolutely no communication between them is allowed on the day of the game. Notice that at no time does Prisoner A know the chosen card.

(Taken from https://www.reddit.com/r/math/comments/44h3tu/interesting_pu..., but quoting since that link has the answer in the top comment.)

Ah, you're right! My mistake.

Edit: I misinterpreted the parent; see below.

If by 'shuffle' you mean like Fisher-Yates, this can't work all the time, since that can produce, e.g. 0, 1, 2, 3, 4, 5 -> 1, 0, 4, 5, 3, which has two cycles. If by 'shuffle' you mean like Fisher-Yates, but not leaving an element in its original position, (i.e., generating a derangement) then this doesn't suffice either, since notice that the same example satisfies that condition and yet still has two cycles. You need Sattolo's algorithm (or something like it) to guarantee a single cycle.

Terry Tao wrote a eulogy for her on his blog: https://terrytao.wordpress.com/2017/07/15/maryam-mirzakhani/

I was auditing that same class. I remember a bunch of us coming to her office hours, and her telling us about her work, and life in Iran.

Truly a sad day.

Hey, this is really cool!

I just tried with Firefox 54.0.1 on macOS, and it seems to work. What version are you using?

Yeah, I think you're thinking of a Bring radical: https://en.wikipedia.org/wiki/Bring_radical

Edit: Oh, but that only lets you solve some quintics. https://news.ycombinator.com/item?id=14686886 describes the functions you need to solve all quintics.

I'm a bit out of my depth here, but I think you can generalize it to differential fields, where you want to figure out e.g. which functions have a closed-form integral. A reference (the only reference?) would be Topological Galois theory: https://www.springer.com/us/book/9783642388705

Thanks, I see why it's confusing. I'll fix it!

Because we start off with the candidate solution matching the real roots, and we continuously move the roots to swap them. At every point of the movement, the candidate solution match the real roots (including order) by assumption, and so if at the end of the movement the candidate solution returns to its initial state, i.e. it's equal to the swapped roots, then that would contradict continuity. Does that make sense?

Yeah. I think I punted on that because, although it's easy for degrees <= 4 (since those have general formulas!), I'd have to implement some root-finding method for degrees >= 5, and somehow preserve the orderings of the roots. Not insurmountable problems -- I might go back and do that someday!

Yes, that's correct. That's the big disadvantage to the topological method I talk about (developed by Vladimir Arnold); it can only prove stuff about the general nth-degree formulas, whereas Galois theory can prove stuff about specific polynomials (e.g., that x^5 – x – 1 is unsolvable in radicals).

On the other hand, the topological method can be easily extended to prove stuff about formulas including other continuous, single-valued operations, like exponential and trigonometric functions, and Galois theory has a harder time with this.

Just JSXGraph: https://jsxgraph.uni-bayreuth.de/wp/index.html

I'm not entirely happy with the framerate I get with the button-triggered animations (especially on mobile) but lack the front-end expertise to track down the problem.

Author here, in case anyone has any questions. :)

Here is a damning Twitter thread comparing the article to Lola's published obituary: https://twitter.com/caulkthewagon/status/864656017480708102

It makes the author and his family a lot less sympathetic.

I found this to be a way better resource than the "Music theory for nerds" article floating around a while ago.

Thanks for clearing it up!

How did the previous story ( https://news.ycombinator.com/item?id=12726970 ) get knocked off the front page so quickly?

Thanks for the recommendations! Did you mean something specific when you referred to "Bostock's notes", or did you just mean his various blog posts and papers?

It should be back up now.

Interesting! How'd you know that about the developer's situation? Digging around kapeli.com, it doesn't talk much about it.

Given that this is hacker news, I'm surprised that no one bothered to write a simulation to sanity-check their answer. Here's a quick and dirty one: http://jsfiddle.net/qc9qk/2/

The mistake that most people seem to be making is using P(biased) and P(fair) instead of P(biased|10 heads) and P(fair|10 heads).

Spoiler: The answer is ~0.75.