Finding finite 𝐵₂-sequences faster (Q4396456)

A sequence of positive integers \(a_1<a_2 <\cdots <a_r\leq n\) is said to be a Sidon sequence or \(B_2\)-sequence if the sums \(a_i+ a_j\), \(1\leq i\leq j\leq r\), are different. The best known upper bound for \(r\) (as proved by the author) is \(r<n^{1/2} +n^{1/4} +1\). On the other hand Bose and Chowla constructed a dense \(B_2\)-sequence as follows: let \(q\) be a power of a prime and \(\theta\) primitive in \(GF(q^2)\); then \(A(q, \theta)= \{a:1 \leq a\leq q^2\), \(\theta^a- \theta\in GF(q)\}\) is a \(B_2\)-sequence of size \(q\). But it is not too easy to determine \(A(q, \theta)\) each time since it is hard to check if \(\theta\) is primitive. In section 2 the author gives a faster alternative to \(A(q, \theta)\) than the original one, and in section 3 he proves a new criterion for a quadratic \(X^2- uX+v\) over \(GF(p)\) \((p\) an odd prime) to be primitive. In section 4 the author gives a very fast construction of a \(B_2\)-sequence extending a construction of I. Z. Ruzsa. It is proved: let \(g\) be a primitive element \(\text{mod }p\). Then the set \[ R(p,f)= \{pfi+ (p-1) g^i \bmod p(p-1): 1\leq i\leq p-1\} \text{ (where } 1\leq f<p-1) \] is a \(B_2\)-sequence modulo \(p(p-1)\).