Avoiding right angles and certain Hamming distances

. 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

m a t h b b F_{q}^{n}

avoiding triangles with all right angles can have size at most

O (n^{2 q - 2})

. Furthermore, asymptotically tight bounds are given for the largest possible size of a subset

A s u b s e t e q m a t h b b F_{q}^{n}

for which

x - y

is not self-orthogonal for any distinct

x, y i n A

. The exact answer is determined for

q = 3

and

n e q u i v 2 p m o d 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.

Review text

This paper is a contribution to additive combinatorics (or to geometry over finite fields). More precisely, the first result of the paper shows that the largest size of a subset of \(\mathbb{F}_q^n\) avoiding right angles (namely, 3 distinct vectors \(x, y, z\) such that \(x -z\) and \(y -z\) are perpendicular to each other) is at most \(O(n^{q-2})\). Let us now move to the second result of the paper. It 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 depends on the residue of \(q\) modulo \(3\). The main technique used in the proofs is the so-called ``slice method. This method is combined with other ideas, including some extremal set theory.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Avoiding right angles and certain Hamming distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6051134)