Avoiding right angles and certain Hamming distances

In this paper we show that the largest possible size of a subset of \(\mathbb{F}_q^n\) 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(n^{q-2})\). This improves on the previously best known bound due to Naslund \...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-12
Main Authors: Bursics, Balázs, Matolcsi, Dávid, Péter Pál Pach, Jakab Schrettner
Format: Article
Language:English
Subjects:
Asymptotic properties
Binary codes
Codes
Lower bounds
Triangles
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we show that the largest possible size of a subset of \(\mathbb{F}_q^n\) 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(n^{q-2})\). This improves on the previously best known bound due to Naslund \cite{Naslund} and refutes a conjecture of Ge and Shangguan \cite{Ge}. A lower bound of \(n^{q/3}\) is also presented. It is also shown that a subset of \(\mathbb{F}_q^n\) avoiding triangles with all right angles can have size at most \(O(n^{2q-2})\). Furthermore, asymptotically tight bounds are given for the largest possible size of a subset \(A\subseteq \mathbb{F}_q^n\) for which \(x-y\) is not self-orthogonal for any distinct \(x,y\in A\). The exact answer is determined for \(q=3\) and \(n\equiv 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.
ISSN:2331-8422