Quelle parameters.tex Sprache: Latech

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%A  parameters.tex        DESIGN documentation              Leonard Soicher
%
%
%
\def\DESIGN{\sf DESIGN}
\def\GRAPE{\sf GRAPE}
\def\nauty{\it nauty}
\def\Aut{{\rm Aut}\,}
\def\x{\times}
\Chapter{Information from design parameters}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Information from $t$-design parameters}

For $t$ a non-negative integer and $v,k,\lambda$ positive integers
with $t\le k\le v$, a $t$-*design*
\index{t-design}
with *parameters*
$t,v,k,\lambda$, or a $t$-$(v,k,\lambda)$ *design*, is a binary block
design with exactly $v$ points, such that each block has size $k$ and
each $t$-subset of the points is contained in exactly $\lambda$ blocks.

\>TDesignLambdas( <t>, <v>, <k>, <lambda> )

A $t$-$(v,k,\lambda)$ design is also an $s$-$(v,k,\lambda_s)$ design
for $0\le s\le t$, where $\lambda_s=\lambda{v-s \choose t-s}/{k-s
\choose t-s}$.

Given a non-negative integer <t>, and positive integers <v>, <k>,
<lambda>, with $<t>\le <k>\le <v>$, this function returns a length
$<t>+1$ list whose $(s+1)$-st element is $\lambda_s$ as defined above,
if all the $\lambda_s$ are integers. Otherwise, `fail' is returned.

\beginexample
gap> TDesignLambdas(5,24,8,1);
[ 759, 253, 77, 21, 5, 1 ]
\endexample

\>TDesignLambdaMin( <t>, <v>, <k> )

Given a non-negative integer <t>, and positive integers <v> and <k>, with
$<t>\le <k>\le <v>$, this function returns the minimum positive <lambda>
such that `TDesignLambdas( <t>, <v>, <k>, <lambda> )' does not return
`fail'.

See "TDesignLambdas".

\beginexample
gap> TDesignLambdaMin(5,24,8);
1
gap> TDesignLambdaMin(2,12,4);
3
\endexample

\>TDesignIntersectionTriangle( <t>, <v>, <k>, <lambda> )

Suppose $D$ is a <t>-(<v>,<k>,<lambda>) design, let $i$ and $j$
be non-negative integers with $i+j\le t$, and suppose $X$ and $Y$
are disjoint subsets of the points of $D$, such that $X$ and $Y$ have
respective sizes $i$ and $j$. The $(i,j)$-*intersection number* is
the number of blocks of $D$ that contain $X$ and are disjoint from $Y$
(this number depends only on <t>, <v>, <k>, <lambda>, $i$ and $j$).

Given a non-negative integer <t>, and positive integers <v>, <k>
and <lambda>, with $<t>\le <k>\le <v>$, this function returns the
*<t>-design intersection triangle*, which is a two dimensional array
whose $(i+1,j+1)$-entry is the $(i,j)$-intersection number for
a <t>-(<v>,<k>,<lambda>) design (assuming such a design exists),
such that $i,j\ge 0$, $i+j\le t$. This function returns `fail' if
`TDesignLambdas(<t>,<v>,<k>,<lambda>)' does. When $=1$, then more
information can be obtained using "SteinerSystemIntersectionTriangle".

\beginexample
gap> TDesignLambdas(2,12,4,3);
[ 33, 11, 3 ]
gap> TDesignIntersectionTriangle(2,12,4,3);
[ [ 33, 22, 14 ], [ 11, 8 ], [ 3 ] ]
gap> TDesignLambdas(2,12,4,2);
fail
gap> TDesignIntersectionTriangle(2,12,4,2);
fail
\endexample

\>SteinerSystemIntersectionTriangle( <t>, <v>, <k> )

A *Steiner system* is a <t>-(<v>,<k>,1) design, and in this case it
is possible to extend the notion of intersection triangle defined in
"TDesignIntersectionTriangle".

Suppose $D$ is a <t>-(<v>,<k>,1) design, with $B$ a block of $D$,
let $i$ and $j$ be non-negative integers with $i+j\le k$, and suppose
$X$ and $Y$ are disjoint subsets of $B$, such that $X$ and $Y$ have
respective sizes $i$ and $j$. The $(i,j)$-*intersection number* is the
number of blocks of $D$ that contain $X$ and are disjoint from $Y$
(this number depends only on <t>, <v>, <k>, $i$ and $j$). Note that
when $i+j\le t$, this intersection number is the same as that defined in
"TDesignIntersectionTriangle" for the general <t>-design case.

Given a non-negative integer <t>, and positive integers <v> and
<k>, with $<t>\le <k>\le <v>$, this function returns the *Steiner
system intersection triangle*, which is a two dimensional array whose
$(i+1,j+1)$-entry is the $(i,j)$-intersection number for a <t>-(<v>,<k>,1)
design (assuming such a design exists), such that $i,j\ge 0$, $i+j\le
k$. This function returns `fail' if `TDesignLambdas(,,,1)' does.

See also "TDesignIntersectionTriangle".

\beginexample
gap> SteinerSystemIntersectionTriangle(5,24,8);
[ [ 759, 506, 330, 210, 130, 78, 46, 30, 30 ],
  [ 253, 176, 120, 80, 52, 32, 16, 0 ], [ 77, 56, 40, 28, 20, 16, 16 ],
  [ 21, 16, 12, 8, 4, 0 ], [ 5, 4, 4, 4, 4 ], [ 1, 0, 0, 0 ], [ 1, 0, 0 ],
  [ 1, 0 ], [ 1 ] ]
gap> TDesignIntersectionTriangle(5,24,8,1);
[ [ 759, 506, 330, 210, 130, 78 ], [ 253, 176, 120, 80, 52 ],
  [ 77, 56, 40, 28 ], [ 21, 16, 12 ], [ 5, 4 ], [ 1 ] ]
\endexample

\>TDesignBlockMultiplicityBound( <t>, <v>, <k>, <lambda> )

Given a non-negative integer <t>, and positive integers <v>, <k> and
<lambda>, with $<t>\le <k>\le <v>$, this function returns a non-negative
integer which is an upper bound on the multiplicity of any block in
any <t>-(<v>,<k>,<lambda>) design (the *multiplicity* of a block in
a block design is the number of times that block occurs in the block
list). In particular, if the value $0$ is returned, then this implies
that a <t>-(<v>,<k>,<lambda>) design does not exist.

Although our bounds are reasonably good, we do not claim that the
returned bound $m$ is always achieved; that is, there may not exist a
<t>-(<v>,<k>,<lambda>) design having a block with multiplicity $m$.

See also "ResolvableTDesignBlockMultiplicityBound".

\beginexample
gap> TDesignBlockMultiplicityBound(5,16,7,5);
2
gap> TDesignBlockMultiplicityBound(2,36,6,1);
0
gap> TDesignBlockMultiplicityBound(2,36,6,2);
2
gap> TDesignBlockMultiplicityBound(2,15,5,2);
0
gap> TDesignBlockMultiplicityBound(2,15,5,4);
2
gap> TDesignBlockMultiplicityBound(2,11,4,6);
3
\endexample

\>ResolvableTDesignBlockMultiplicityBound( <t>, <v>, <k>, <lambda> )

A *resolution* of a block design is a partition of the blocks into
subsets, each of which forms a partition of the point set, and a block
design is *resolvable* if it has a resolution.

Given a non-negative integer <t>, and positive integers <v>, <k> and
<lambda>, with $<t>\le <k>\le <v>$, this function returns a non-negative
integer which is an upper bound on the multiplicity of any block in any
resolvable <t>-(<v>,<k>,<lambda>) design (the *multiplicity* of a block
in a block design is the number of times that block occurs in the block
list). In particular, if the value $0$ is returned, then this implies
that a resolvable <t>-(<v>,<k>,<lambda>) design does not exist.

Although our bounds are reasonably good, we do not claim that the returned
bound $m$ is always achieved; that is, there may not exist a resolvable
<t>-(<v>,<k>,<lambda>) design having a block with multiplicity $m$.

See also "TDesignBlockMultiplicityBound".

\beginexample
gap> ResolvableTDesignBlockMultiplicityBound(5,12,6,1);
1
gap> ResolvableTDesignBlockMultiplicityBound(2,21,7,3);
0
gap> TDesignBlockMultiplicityBound(2,21,7,3);
1
gap> ResolvableTDesignBlockMultiplicityBound(2,12,4,3);
1
gap> TDesignBlockMultiplicityBound(2,12,4,3);
2
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Information from (mixed) orthogonal array parameters}

For integers $N,k,s,t$, with $N,k>0$, $s>1$, and $0\le t\le k$,
an *orthogonal array* \index{orthogonal array}
OA$(N,k,s,t)$ is an $N\times k$ array, in which the entries come from a
set of size $s$ of *symbols*, with the property that in any $N\times t$
subarray, every possible $t$-tuple of symbols occurs as a row equally
often (which must be $N/s^t$ times).

For integers $N,k_1,\ldots,k_w,s_1,\ldots,s_w,t$, with
$w,N,k_1,\ldots,k_w>0$, $s_1,\ldots,s_w>1$, and $0\le t\le k:=k_1+\cdots+k_w$,
a *mixed orthogonal array*
\index{mixed orthogonal array}
OA$(N,s_1^{k_1},\ldots,s_w^{k_w},t)$ is an $N\times k$
array, in which the entries in the first
$k_1$ columns come from a set of symbols of size $s_1$, the entries
in the next $k_2$ columns come from a set of symbols of size $s_2$,
and so on, with the property that in any $N\times t$ subarray, every
possible $t$-tuple of symbols occurs as a row equally often.
Clearly, a mixed orthogonal array OA$(N,s^k,t)$ is the same thing as an
orthogonal array OA$(N,k,s,t)$.

The rows of an orthogonal array or mixed orthogonal array are called *runs*.
The *multiplicity* of a run is the number of times it appears as a row
in the array.

\>OARunMultiplicityBound( <N>, <k>, <s>, <t> )

Suppose <N>, <k>, <s>, and <t> are integers, with <N>, <k> positive,
$<s> > 1$, and $0\le <t>\le <k>$.  Then this function returns an upper
bound on the multiplicity of any run in an orthogonal array OA$(N,k,s,t)$.

An upper bound on the multiplicity of a run in a mixed orthogonal array
can be obtained by replacing <k> and <s> by non-empty lists of the same
length, $w$ say, of positive integers, such that $0\le <t> \le$ `Sum(<k>)',
and each entry of <s> is at least 2.  Then the function returns an
upper bound on the multiplicity of any run in a mixed orthogonal array
OA$(N,s[1]^{k[1]},...,s[w]^{k[w]},t)$.

If the value $0$ is returned, then this implies that an orthogonal array
or mixed orthogonal array with the given parameters does not exist.

We do not claim that the returned upper bound $m$ is achieved; that
is, there may well be no (mixed) orthogonal array with the given
parameters having a run with multiplicity $m$.

\beginexample
gap> OARunMultiplicityBound(81,14,3,3);
1
gap> OARunMultiplicityBound(81,15,3,3);
0
gap> OARunMultiplicityBound(36,[18,1,1],[2,3,6],2);
1
gap> OARunMultiplicityBound(72,7,6,2);
2
gap> OARunMultiplicityBound(72,8,6,2);
1
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Block intersection polynomials}

In \cite{CaSo}, Cameron and Soicher introduce block intersection
polynomials and their applications to the study of block designs.
Here we give functions to construct and analyze block intersection
polynomials.

\>BlockIntersectionPolynomial(<x>, <m>, <lambdavec> )

For $k$ a non-negative integer, define the polynomial
$P(x,k)=x(x-1)\cdots(x-k+1)$. Let $s$ and $t$ be non-negative
integers, with $s\ge t$, and let $m_0,\ldots,m_s$ and
$\lambda_0,\ldots,\lambda_t$ be rational numbers. Then the *block
intersection polynomial* for the sequences $[m_0,\ldots,m_s]$,
$[\lambda_0,\ldots,\lambda_t]$ is defined to be
$$\sum_{j=0}^t{t\choose j}P(-x,t-j)[P(s,j)\lambda_j-\sum_{i=j}^s P(i,j)m_i],$$
and is denoted by $B(x,[m_0,\ldots,m_s],[\lambda_0,\ldots,\lambda_t]).$

Now suppose <x> is an indeterminate over the rationals, and <m> and
<lambdavec> are non-empty lists of rational numbers, such that the length
of <lambdavec> is not greater than that of <m>.  Then this function
returns the block intersection polynomial $B(<x>,<m>,<lambdavec>)$.

The importance of a block intersection polynomial is as follows.
Let $D=(V,{\cal B})$ be a block design, let $S\subseteq V$, with $s=|S|$,
and for $i=0,\ldots,s$, suppose that $m_i$ is a non-negative integer
with $m_i\le n_i$, where $n_i$ is the number of blocks intersecting $S$
in exactly $i$ points. Let $t$ be a non-negative *even* integer with $t\le
s$, and suppose that, for $j=0\ldots,t$, we have $\lambda_j=1/{s\choose
j}\sum_{T\subseteq S,|T|=j}\lambda_T$, where $\lambda_T$ is the
number of blocks of $D$ containing $T$.  Then the block intersection
polynomial $B(x)=B(x,[m_0,\ldots,m_s],[\lambda_0,\ldots,\lambda_t])$
is a polynomial with integer coefficients, and $B(n)\ge 0$ for every
integer $n$. (These conditions can be checked using the function
"BlockIntersectionPolynomialCheck".) In addition, if $B(n)=0$ for some
integer $n$, then $m_i=n_i$ for $i\not\in\{n,n+1,\ldots,n+t-1\}$.

For more information on block intersection polynomials and their
applications, see \cite{CaSo} and \cite{Soi10}.

\beginexample
gap> x:=Indeterminate(Rationals,1);
x_1
gap> m:=[0,0,0,0,0,0,0,1];;
gap> lambdavec:=TDesignLambdas(6,14,7,4);
[ 1716, 858, 396, 165, 60, 18, 4 ]
gap> B:=BlockIntersectionPolynomial(x,m,lambdavec);
1715*x_1^6-10269*x_1^5+34685*x_1^4-69615*x_1^3+84560*x_1^2-56196*x_1+15120
gap> Factors(B);
[ 1715*x_1-1715,
  x_1^5-1222/245*x_1^4+3733/245*x_1^3-6212/245*x_1^2+5868/245*x_1-432/49 ]
gap> Value(B,1);
0
\endexample

\>BlockIntersectionPolynomialCheck(<m>, <lambdavec>)

Suppose <m> is a list of non-negative integers, and <lambdavec> is a
list of non-negative rational numbers, with the length of <lambdavec>
odd and not greater than the length of <m>.

Then, for <x> an indeterminate over the rationals, this function
checks whether `BlockIntersectionPolynomial(<x>,<m>,<lambdavec>)' is a
polynomial over the integers and has a non-negative value at each integer.
The function returns `true' if this is so; else `false' is returned.

See also "BlockIntersectionPolynomial".

\beginexample
gap> m:=[0,0,0,0,0,0,0,1];;
gap> lambdavec:=TDesignLambdas(6,14,7,4);
[ 1716, 858, 396, 165, 60, 18, 4 ]
gap> BlockIntersectionPolynomialCheck(m,lambdavec);
true
gap> m:=[1,0,0,0,0,0,0,1];;
gap> BlockIntersectionPolynomialCheck(m,lambdavec);
false
\endexample

quality100%

¤ Dauer der Verarbeitung: 0.32 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.