Bounds on the maximum number of vectors with given scalar products

Abstract

Suppose <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L"> <mml:semantics> <mml:mi>L</mml:mi> <mml:annotation encoding="application/x-tex">L</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are sets of real numbers, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper V equals StartSet upsilon 1 comma ellipsis comma upsilon Subscript m Baseline EndSet"> <mml:semantics> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>=</mml:mo> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>υ<!-- υ --></mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mo>…<!-- … --></mml:mo> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>υ<!-- υ --></mml:mi> <mml:mi>m</mml:mi> </mml:msub> </mml:mrow> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">V = \{ {\upsilon _1}, \ldots ,{\upsilon _m}\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a collection of vectors in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper R Superscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>R</mml:mi> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{R^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, having <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> nonzero coordinates all from <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and satisfying <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upsilon Subscript i Baseline comma upsilon Subscript j Baseline right-parenthesis element-of upper L"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>υ<!-- υ --></mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>υ<!-- υ --></mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mi>L</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">({\upsilon _i},{\upsilon _j}) \in L</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="i not-equals j"> <mml:semantics> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>≠<!-- ≠ --></mml:mo> <mml:mi>j</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">i \ne j</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Theorem 1.1 establishes a polynomial upper bound for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartAbsoluteValue upper V EndAbsoluteValue"> <mml:semantics> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>V</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\left | V \right |</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, generalizing previous results for subsets of a set and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis 0 comma plus-or-minus 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mo>±<!-- ± --></mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(0, \pm 1)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-vectors. Theorem 1.4 asserts that if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartAbsoluteValue upper L EndAbsoluteValue equals s"> <mml:semantics> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>L</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>s</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\left | L \right | = s</mml:annotation> </mml:semantics> </mml:math> </inline-formula> then <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartAbsoluteValue upper V EndAbsoluteValue less-than-or-slanted-equals StartBinomialOrMatrix n plus s Choose s EndBinomialOrMatrix"> <mml:semantics> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>V</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo>⩽<!-- ⩽ --></mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtable rowspacing="4pt" columnspacing="1em"> <mml:mtr> <mml:mtd> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>s</mml:mi> </mml:mrow> </mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd> <mml:mi>s</mml:mi> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\left | V \right | \leqslant \left ( {\begin {array}{*{20}{c}} {n + s} \\ s \\ \end {array} } \right )</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. For <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M equals StartSet negative 1 comma 1 EndSet"> <mml:semantics> <mml:mrow> <mml:mi>M</mml:mi> <mml:mo>=</mml:mo> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">M = \{ - 1,1\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L equals left-bracket minus left-parenthesis k minus 1 right-parenthesis comma k minus 1 right-bracket"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>=</mml:mo> <mml:mo stretchy="false">[</mml:mo> <mml:mo>−<!-- − --></mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">L = [ - (k - 1),k - 1]</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, Theorem 1.5 gives <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartAbsoluteValue upper V EndAbsoluteValue less-than-or-slanted-equals 2 Superscript k minus 1 Baseline StartBinomialOrMatrix n Choose k minus 1 EndBinomialOrMatrix slash k"> <mml:semantics> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>V</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:mo>⩽<!-- ⩽ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtable rowspacing="4pt" columnspacing="1em"> <mml:mtr> <mml:mtd> <mml:mi>n</mml:mi> </mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\left | V \right | \leqslant {2^{k - 1}}\left ( {\begin {array}{*{20}{c}} n \\ {k - 1} \\ \end {array} } \right )/k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where equality holds if and only if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper V"> <mml:semantics> <mml:mi>V</mml:mi> <mml:annotation encoding="application/x-tex">V</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a "signed" <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis n comma k comma k minus 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(n,k,k - 1)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> Steiner-system.

Locations

• Proceedings of the American Mathematical Society - View - PDF