13
$\begingroup$

This is a direct follow-up to this question, which I think is interesting enough to be a separate problem. Please check that post out too in case there are ideas there that might transfer here.

In the post linked, they found numerically that for odd primes $p \equiv 1 \pmod{4}$, the sum of all $n$ such that $(n^2+2n+1 \ \mathrm{mod} p) < (n^2 \ \mathrm{mod} p)$ is exactly $\frac{7}{24}(p^2-1)$. It is natural to generalise this for $p \equiv 3 \pmod{4}$, and you won't believe what I found! Here's some Sage code:

x = var('x')
for p in prime_range(6, 1001):
    if p % 4 != 3: continue
    ns = [n for n in range(p) if (n^2 + 2*n + 1) % p < (n^2) % p] # your condition
    R.<t> = NumberField(x^2 + p) # setup Q[sqrt(-p)]
    assert sum(ns) == (p^2 - 1) * 7 / 24 - R.class_number() # observed = ???

As annotated above, I conjecture that for odd primes $p > 3$ satisfying $p \equiv 3 \pmod{4}$, we have

$$ \sum_{0 \leq n < p} n \cdot [(n+1)^2\,\mathrm{mod}\, p \leq n^2\,\mathrm{mod}\, p] = \frac{7}{24}(p^2-1)-h(\sqrt{-p}). $$

Feel free to play with the Sage script above. I suspect that there might be some "symmetry" or relation with quadratic residues, since it is well known that the class number is (-1 / p) times sum of n * (n | p).

I will set a bounty when I can.

$\endgroup$
11
  • $\begingroup$ Yes, this might be finally a simple method to calculate the class number. Check this desmos: desmos.com/calculator/gnfkwahnbf you rotate and shift by 1; they line up almost perfectly only differ in three places: $0$, middle and $p$. $\endgroup$
    – ploosu2
    Feb 15, 2023 at 21:16
  • 1
    $\begingroup$ PARI/GP will be a much better tool for this purpose than Desmos. $\endgroup$
    – Peter
    Feb 16, 2023 at 14:37
  • 2
    $\begingroup$ What is $h(-p)$ and why do you have $h(-\sqrt{p})$ later ? $\endgroup$
    – Peter
    Feb 16, 2023 at 14:39
  • 1
    $\begingroup$ Combining the techniques from my answer in the linked problem, with Will Jagy's formula below, should yield this. Note that the only thing mysterious in the calculation with $p \equiv 3 \pmod 4$ will be the sum of quadratic residues which should exactly be taken care of by that class number formula. $\endgroup$ Feb 16, 2023 at 20:28
  • 2
    $\begingroup$ Well, it works. Highlights include, with prime $q = 4 w + 3, $ $$ \sum_{j=1}^w \left\lfloor \sqrt{jq} \right\rfloor = 2w^2 -\sum_{x=1}^{2w} \left\lfloor \frac{ x^2}{q} \right\rfloor $$ and $$ \sum_{x=1}^{2w} \left\lfloor \frac{ x^2}{q} \right\rfloor = \frac{(q-1)(q-11)}{24} + \frac{1+ h( \sqrt {-q} )}{2} $$ $\endgroup$
    – Will Jagy
    Feb 20, 2023 at 4:13

0

You must log in to answer this question.

Browse other questions tagged .