(Dual) Plotkin Bound

An orthogonal array OA(M, s, Sb, k) can exist only if

M ≥ bs$\displaystyle \left(\vphantom{1-\frac{(b−1)s}{b(k+1)}}\right.$1 – $\displaystyle {\frac{{(b−1)s}}{{b(k+1)}}}$$\displaystyle \left.\vphantom{1-\frac{(b−1)s}{b(k+1)}}\right)$.

This inequality is trivially satisfied and consequently the theorem gives no information if s ≥ b(k + 1)/(b−1). For b = 2 the bound was first established in [1], the general result is given in [2] and [3]. [2] gives an elementary proof whereas in [3] the dual Plotkin bound is derived from the linear programming bound.

The dual of this bound is the Plotkin bound [4], which states that for all (s, N, d)-codes over Fb with bd > (b−1)s we have

N ≤ $\displaystyle {\frac{{bd}}{{bd-(b−1)s}}}$.

It is now known that both bounds are implied by the linear programming bound for orthogonal arrays. There also exists a generalization for OOAs with arbitrary depth.

Application to Nets and Sequences

In [5, Theorem 4.4.14] the dual Plotkin bound is used for establishing the corresponding result for (t, t + k, s)-nets.

Niederreiter applies this result to (t, t + k, s + 1)-nets with k = ⌊s – s/b⌋ + 1 and derives 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 it is shown in [6, Theorem 8] that

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

and therefore

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

This is a better bound than the one obtained using the Rao bound for orthogonal arrays, and for b > 2 also better than the one resulting from the generalized Rao bound for OOAs. However, stronger bounds can be derived for all bases from the generalized Plotkin bound for OOAs.

See Also

References

[1]J. Friedman.
On the bit extraction problem.
In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 314–319. IEEE Press, 1992.
[2]Jürgen Bierbrauer.
Bounds on orthogonal arrays and resilient functions.
Journal of Combinatorial Designs, 3(3):179–183, 1995.
doi:10.1002/jcd.3180030304 MR1324473 (96d:05023)
[3]Jürgen Bierbrauer, K. Gopalakrishnan, and Douglas R. Stinson.
Orthogonal arrays, resilient functions, error-correcting codes, and linear programming bounds.
SIAM Journal on Discrete Mathematics, 9(3):424–452, 1996.
doi:10.1137/S0895480194270950 MR1402189 (97f:05028)
[4]Morris Plotkin.
Binary codes with specified minimum distance.
IEEE Transactions on Information Theory, 6(4):445–450, September 1960.
[5]Kenneth Mark Lawrence.
Combinatorial Bounds and Constructions in the Theory of Uniform Point Distributions in Unit Cubes, Connections with Orthogonal Arrays and a Poset Generalization of a Related Problem in Coding Theory.
PhD thesis, University of Wisconsin, Madison, 1995.
[6]Harald Niederreiter and Chaoping Xing.
Quasirandom points and global function fields.
In S. Cohen and Harald Niederreiter, editors, Finite Fields and Applications, volume 233 of Lect. Note Series of the London Math. Soc., pages 269–296. Cambridge University Press, 1996.

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. “(Dual) Plotkin Bound.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CBoundPlotkin.html

Show usage of this method