On Legendre Symbol Lattices

In an earlier paper Hubert, Mauduit and Sarkozy introduced pseu- dorandom measures for pseudorandomness of binary lattices, and they gave con- structions for binary lattices with strong pseudorandom properties. They gave nearly optimal upper bounds for the pseudorandom measures of the lattices con- structed. However, these early constructions also have disadvantages: they are rather artificial, and their implementation is complicated. Thus another construc- tion is presented here which is based on the use of the Legendre symbol. This construction is much more natural and flexible than the earlier ones, and it can be implemented more easily. However, there is a price paid for this: to give upper bounds for the pseudorandom measures one needs the flexibility and generality of Weil’s theorem, and here in the two dimensional situation this approach leads to weaker bounds than the optimal ones.