6
$\begingroup$

Let $A$ be a finite abelian group. Let $q:A\times A\to \mathbb{C}^{\times}$ be a non-degenerate bicharacter (that is: for every $a\in A$ $q(a,-)$ and $q(-,a)$ are characters of $A$, which are trivial if and only if $a=1$).

What can we say about the sum $$\sum_{a\in A}q(a,a)$$ (where the sum is being taken in $\mathbb{C}$?)

Can this sum be expressed by any invariants of $q$ or of $A$?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ If $A$ is cyclic then this is an example of a quadratic Gauss sum, which have been computed by Gauss. $\endgroup$
    – user85913
    Commented Jul 12, 2017 at 14:44
  • $\begingroup$ @t.c., I think that further $\lvert A\rvert$ should be prime, no? $\endgroup$
    – LSpice
    Commented Jul 12, 2017 at 16:49
  • 1
    $\begingroup$ @LSpice, I'm not sure whether calling the sum a ``quadratic Gauss sum'' agrees with standard usage when $|A|$ is not prime, but I think at least that the computation is still ok: if $A=\mathbb Z/n$, then $q$ has the form $q(a,b)=\exp(2\pi i abc /n)$ for some $c\in (\mathbb Z/n)^*$, and the sum is $\sum_{a\in \mathbb Z/n} \exp(2\pi i a^2 c/n)$, which I believe was computed by Gauss. $\endgroup$
    – user85913
    Commented Jul 13, 2017 at 8:07
  • $\begingroup$ @t.c. I can see how to reduce to the case where $|A|$ is a prime power. However: how do we reduce the non-cyclic case to the cyclic case? $\endgroup$
    – Ehud Meir
    Commented Jul 13, 2017 at 11:42
  • $\begingroup$ @EhudMeir The reduction to the cyclic case is not at all obvious (to me). But Chapter 5 of Scharlau's book Quadratic and Hermitian Forms appears to be very relevant. $\endgroup$
    – user85913
    Commented Jul 13, 2017 at 13:07

1 Answer 1

Reset to default
2
$\begingroup$

In brief: such Gauss sums are easy to compute (when provided in a "fair" manner), and should be considered as invariants of the bicharacter (rather than the other way around).

In more detail: Building on work of Basak and Johnson, my collaborators and I showed in Appendix C here that there is a polynomial time algorithm to compute such a (homogeneous) quadratic Gauss sum. As you probably know, Wall classified irreducible metric groups. Basak and Johnson essentially pointed the way to an algorithmic classification of general metric groups into irreducible pieces. We did the complexity analysis of this approach. The Gauss sum of a reducible metric group is the product of the Gauss sums of its summands, and these can each be looked up in a table (due to Gauss, Wall,…) so that finishes the job.

For an alternative (and more general) approach, I quite enjoyed this paper by Cai, Chen, Lipton, and Lu: On Tractable Exponential Sums.

It is perhaps worth stressing that when I say "polynomial time," I mean that $A$ is a finite abelian group given explicitly in terms of its list of primary factors whose orders are written in binary. (On one hand, it would be unfair to require us to factorize $A$ first; on the other hand, it would also be unfair if we could just sum over all elements of $A$ directly.) We are given q as a matrix with integer entries.

As far as your last question (can we compute the sum from invariants of the metric group): the more helpful way for us to think about things is the converse. That is, the Gauss sum is itself an invariant of quadratic forms that packages up into a homomorphism from the Witt group to $U(1)$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ As someone at the end of the alphabet, I'm sensitive about "et al." attributions; so, since space here is not at a premium, while editing in the names of the papers, I also went ahead and expanded out "Cai et al." I hope that was all right. $\endgroup$
    – LSpice
    Commented Jul 17 at 2:18
  • 1
    $\begingroup$ No problem, thanks! $\endgroup$
    – Eric S.
    Commented Jul 17 at 2:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .