My gut, reading the HN title, was "half the time". I had to read the article, to see how many words piled up before he said that.
Of course, considering finite fields of prime power order, one might leap to the conclusion "a quarter of the time". One can adjoin "i" for prime powers p^n for half the primes and odd n.
Alas, this be wrong, for an amusing reason.
c1ccccc1•2mo ago
Why is that? My guess would be that you could adjoin an i all the time to the p^n field and get the p^2n field, as long as you had p = 4k + 3. But that's admittedly based on approximately zero thinking.
EDIT: Looking things up indicates that if n is even, there's already a square root of -1 in the field, so we can't add another. So now I believe the 1/4 of the time thing you mentioned, and can't see how that's wrong.
dperrin•2mo ago
Spitballing here, but I suspect it's a density thing. If you are considering all prime powers up to some bound N, then the density of prime powers (edit: of size p^n with n > 1) approaches 0 as N tends to infinity. So rather than things being 1/4 like our intuition says, it should unintuitively be 1/2. I haven't given this much thought, but I suspect this based on checking some examples in Sage.
c1ccccc1•2mo ago
Oh, so just a probability density thing where we sample q and check if it's p^n (retrying if not) rather than sampling p and n separately and computing q=p^n? I guess that's probably what the they were going for, yeah.
Syzygies•2mo ago
Of course, considering finite fields of prime power order, one might leap to the conclusion "a quarter of the time". One can adjoin "i" for prime powers p^n for half the primes and odd n.
Alas, this be wrong, for an amusing reason.
c1ccccc1•2mo ago
EDIT: Looking things up indicates that if n is even, there's already a square root of -1 in the field, so we can't add another. So now I believe the 1/4 of the time thing you mentioned, and can't see how that's wrong.
dperrin•2mo ago
c1ccccc1•2mo ago
Syzygies•2mo ago