Avoiding right angles and certain Hamming distances

DOI10.1016/J.LAA.2023.07.028MaRDI QIDQ6051134zbMATH OpenOpenAlexFDO

Authors Balázs Bursics, Dávid Matolcsi, Péter Pál Pach, Jakab Schrettner

Publication date 19 September 2023

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2012.08232

zbMATH Keywords

Hamming distancepolynomial methodright angle free setsslice rank

Mathematics Subject Classification ID

Arithmetic combinatorics; higher degree uniformity (11B30) Other combinatorial number theory (11B75) Multilinear algebra, tensor calculus (15A69)

Abstract: 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 $Asubseteqmathbb{F}_q^n$ for which $x-y$ is not self-orthogonal for any distinct $x,yinA$. The exact answer is determined for $q=3$ and $nequiv2pmod3$. 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.

Recommendations

• Maximum subsets of \(\mathbb{F}^n_q\) containing no right angles
• Occurrence of right angles in vector spaces over finite fields
• On point sets in vector spaces over finite fields that determine only acute angle triangles
• A note on a problem of Erdős on right angles
• scientific article; zbMATH DE number 7731180

Cites work

• A new proof of several inequalities on codes and sets
• An upper bound for the cardinality of an s-distance subset in real euclidean space
• Families of finite sets in which no set is covered by the union of two others
• Four fundamental parameters of a code and their combinatorial significance
• How large dimension guarantees a given angle?
• scientific article; zbMATH DE number 3848141 (Why is no real title available?)
• Occurrence of right angles in vector spaces over finite fields
• On a packing and covering problem
• On a problem of Erdős on fractal combinatorial geometry
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• On t-designs
• Orthogonal vectors in the n-dimensional cube and codes with missing distances
• Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
• The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)

Cited in

(2)

• Small codes
• Partition rank and partition lattices

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)