Maximum pairwise-product of a set in $Z_p$ Let $A$ be a subset of $[1,p-1]$ of size $N$, for a prime $p$.
My question is what is the most efficient algorithm to find: $$\max \{(x \cdot x')~mod~p~|~ x,x'\in A\}$$
In other words, how efficiently can we compute the maximum pairwise-product values for a set $A$ in the field $Z_p$?
 A: I'll take a stab at this.
As pointed out at the comments, one can obtain the characteristic vector $\chi_{S+T}$ of the multiset
$$S+T = \{s+t \mid s \in S, t \in T\},$$
by defining $\chi_S$ to be the characteristic vector of a set $S$ in $\mathbb{Z}_p$.  Then
$$\chi_{S+T} = \chi_S \ast \chi_T,$$
where $\ast$ is the convolution operator. Now using the Fourier transform $\mathcal{F}$  property gives
$$\mathcal{F}(f\ast g) = \mathcal{F}(f) \times \mathcal{F}(g),$$
where $\times$ represents pointwise multiplication of functions. Thus we have
$$\mathcal{F}(\chi_{S+T}) = \mathcal{F}(\chi_S) \times \mathcal{F}(\chi_T).$$
The Fourier transform is just the complex DFT with length $p.$
Now, let $S_1=A,$ $S_k=S_{k-1} + S_1,$ for $k=2,\ldots,\max(S_1).$ Each one of these operations will be performed in the Fourier domain via
$$\mathcal{F}(\chi_{S_{k-1}+S_1}) = \mathcal{F}(\chi_{S_{k-1}}) \times 
\mathcal{F}(\chi_{S_1}).$$
By carrying out the convolution $\max(S_1)$ times you ensure that you can allow for all the elements of $S_1$ being used as multipliers.
However, you do not want to multiply by elements in the complement of $S_1.$
Example: Let $p=7,$ and $S_1=A=\{a_1,a_2,a_3\}=\{2,4,5\},$ then you'd perform the convolution 5 times
but you'd want to avoid "multiplying" by 1,3, or 6. A sum of the form
$a_i+a_j$ is valid (2 is in $A$) and can contribute to the maximum, but the single term sum $a_i$ is not (1 is not in $A$), $a_i+a_j+a_k$ is not (3 is not in $A$), etc.
Note that we can always ignore $0$ even if it is in $A$ since it won't give a maximum value if part of a product.
So what you really want to do now, having computed the $S_k$ is to do the following (recall $S_1=A$):
Let $\textrm{maxprod}=0.$
For $k$ ranging between $1$ and $\max(S_1)$ do:
if $k\in S_1$ (i.e., it is a legitimate multiplier which should be taken into account) then update via
$$
\textrm{maxprod}=\max( \max(S_k), \textrm{maxprod})
$$
$~~~$else don't update.
End do:
