Generalized (Dual) Plotkin Bound for OOAs

In [1, Theorem 2] the Plotkin bound for linear codes is generalized to NRT space. Using duality theory [2] the following bound for linear ordered orthogonal arrays is obtained: For every linear OOA(bm, s, Sb, T , k) we have

$\displaystyle {\frac{{k+1}}{{s}}}$(bTs−m – 1) ≤ bTs−mρT

with

ρT = T – $\displaystyle \sum_{{i=1}}^{{T}}$$\displaystyle {\frac{{1}}{{b^{i}}}}$ = T – $\displaystyle {\frac{{b^{T}−1}}{{b^{T}(b−1)}}}$.

It is easy to see that the original Plotkin bound is obtained for T = 1.

In [3, Theorem 5] and [4, Theorem 6] this bound is derived for arbitrary (not necessarily linear) OOAs from the linear programming bound for OOAs.

Application to Nets and Sequences

In [5, Chapter 3] and [6] Schürer uses the dual Plotkin bound for OOAs for deriving the following bound for (t, s)-sequences: Let tb(s) be the minimum t such that a (t, s)-sequence in base b can exist. Then

tb(s) ≥ $\displaystyle {\frac{{1}}{{b−1}}}$ s – O(log s)

and therefore

$\displaystyle \liminf_{{s\to\infty}}^{}$$\displaystyle {\frac{{t_{b}(s)}}{{s}}}$ ≥ $\displaystyle {\frac{{1}}{{b−1}}}$.

The bound 1/(b−1) is the best result for digital as well as arbitrary (t, s)-sequences known today.

See Also

References

[1]Michael Yu. Rosenbloom and Michael A. Tsfasman.
Codes for the m-metric.
Problems of Information Transmission, 33:55–63, 1997.
[2]Harald Niederreiter and Gottlieb Pirsic.
Duality for digital nets and its applications.
Acta Arithmetica, 97(2):173–182, 2001.
MR1824983 (2001m:11130)
[3]William J. Martin and Terry I. Visentin.
A dual Plotkin bound for (T , M, S)-nets.
IEEE Transactions on Information Theory, 53(1):411–415, January 2007.
doi:10.1109/TIT.2006.887514 MR2292900 (2007m:94258)
[4]Jürgen Bierbrauer.
A direct approach to linear programming bounds for codes and tms-nets.
Designs, Codes and Cryptography, 42(2):127–143, February 2007.
doi:10.1007/s10623-006-9025-6 MR2287187
[5]Rudolf Schürer.
Ordered Orthogonal Arrays and Where to Find Them.
PhD thesis, University of Salzburg, Austria, August 2006. PDF
[6]Rudolf Schürer.
A new lower bound on the t-parameter of (t, s)-sequences.
In Alexander Keller, Stefan Heinrich, and Harald Niederreiter, editors, Monte Carlo and Quasi-Monte Carlo Methods 2006, pages 623–632. Springer-Verlag, 2008.
doi:10.1007/978-3-540-74496-2_37

Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Generalized (Dual) Plotkin Bound for OOAs.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2024-09-05. http://mint.sbg.ac.at/desc_OBoundPlotkin.html

Show usage of this method