2020/12/15 by Balázs Bursics, Dávid Matolcsi, Bursics, Balázs +5
Computer Science · Engineering · #Coding theory and cryptography #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Number Theory (math.NT) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2012.08232
openalex publication_date 2020/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we show that the largest possible size of a subset of \mathbbFqn avoiding right angles, that is, distinct vectors x,y,z such that x-z and y-z are perpendicular to each other is at most O(nq-2). This improves on the previously best known bound due to Naslund \citeNaslund and refutes a conjecture of Ge and Shangguan \citeGe. A lower bound of nq/3 is also presented. It is also shown that a subset of \mathbbFqn avoiding triangles with all right angles can have size at most O(n2q-2). Furthermore, asymptotically tight bounds are given for the largest possible size of a subset A⊆ \mathbbFqn for which x-y is not self-orthogonal for any distinct x,y∈ A. The exact answer is determined for q=3 and n≡ 2\pmod 3. Our methods can also be used to bound the maximum possible size of a binary code where no two codewords have Hamming distance divisible by a fixed prime q. Our lower- and upper bounds are asymptotically tight and both are sharp in infinitely many cases.