Quellcode-Bibliothek CHAP002.htm Sprache: unbekannt

<html><head><title>[design] 2 Information from design parameters</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP001.htm">Previous</a>] [<a href ="CHAP003.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>2 Information from design parameters</h1>

<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP002.htm#SECT001">Information from $t$-design parameters</a>
<li> <A HREF="CHAP002.htm#SECT002">Information from (mixed) orthogonal array parameters</a>
<li> <A HREF="CHAP002.htm#SECT003">Block intersection polynomials</a>
</ol>


<h2><a name="SECT001">2.1 Information from $t$-design parameters</a></h2>

For <var>t</var> a non-negative integer and <var>v,k,lambda</var> positive integers
with <var>tleklev</var>, a <var>t</var>-design
<a name = "I0"></a>

with parameters
<var>t,v,k,lambda</var>, or a <var>t</var>-<var>(v,k,lambda)</var> design, is a binary block
design with exactly <var>v</var> points, such that each block has size <var>k</var> and
each <var>t</var>-subset of the points is contained in exactly <var>lambda</var> blocks.

<a name = "SSEC001.1"></a>
<li><code>TDesignLambdas( </code><var>t</var><code>, </code><var>v</var><code>, </code><var>k</var><code>, </code><var>lambda</var><code> )</code>

A <var>t</var>-<var>(v,k,lambda)</var> design is also an <var>s</var>-<var>(v,k,lambdas)</var> design
for <var>0leslet</var>, where <var>lambdas=lambdav-s chooset-s/k-s
chooset-s</var>.

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

<pre>
gap> TDesignLambdas(5,24,8,1);
[ 759, 253, 77, 21, 5, 1 ]
</pre>

<a name = "SSEC001.2"></a>
<li><code>TDesignLambdaMin( </code><var>t</var><code>, </code><var>v</var><code>, </code><var>k</var><code> )</code>

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

See <a href="CHAP002.htm#SSEC001.1">TDesignLambdas</a>.

<pre>
gap> TDesignLambdaMin(5,24,8);
1
gap> TDesignLambdaMin(2,12,4);
3
</pre>

<a name = "SSEC001.3"></a>
<li><code>TDesignIntersectionTriangle( </code><var>t</var><code>, </code><var>v</var><code>, </code><var>k</var><code>, </code><var>lambda</var><code> )</code>

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

Given a non-negative integer <var>t</var>, and positive integers <var>v</var>, <var>k</var>
and <var>lambda</var>, with <var><var>t</var>le<var>k</var>le<var>v</var></var>, this function returns the
<var>t</var>-design intersection triangle, which is a two dimensional array
whose <var>(i+1,j+1)</var>-entry is the <var>(i,j)</var>-intersection number for
a <var>t</var>-(<var>v</var>,<var>k</var>,<var>lambda</var>) design (assuming such a design exists),
such that <var>i,jge0</var>, <var>i+jlet</var>. This function returns <code>fail</code> if
<code>TDesignLambdas(</code><var>t</var><code>,</code><var>v</var><code>,</code><var>k</var><code>,</code><var>lambda</var><code>)</code> does. When <var><var>lambda</var>=1</var>, then more
information can be obtained using <a href="CHAP002.htm#SSEC001.4">SteinerSystemIntersectionTriangle</a>.

<pre>
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
</pre>

<a name = "SSEC001.4"></a>
<li><code>SteinerSystemIntersectionTriangle( </code><var>t</var><code>, </code><var>v</var><code>, </code><var>k</var><code> )</code>

A Steiner system is a <var>t</var>-(<var>v</var>,<var>k</var>,1) design, and in this case it
is possible to extend the notion of intersection triangle defined in
<a href="CHAP002.htm#SSEC001.3">TDesignIntersectionTriangle</a>.

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

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

See also <a href="CHAP002.htm#SSEC001.3">TDesignIntersectionTriangle</a>.

<pre>
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 ] ]
</pre>

<a name = "SSEC001.5"></a>
<li><code>TDesignBlockMultiplicityBound( </code><var>t</var><code>, </code><var>v</var><code>, </code><var>k</var><code>, </code><var>lambda</var><code> )</code>

Given a non-negative integer <var>t</var>, and positive integers <var>v</var>, <var>k</var> and
<var>lambda</var>, with <var><var>t</var>le<var>k</var>le<var>v</var></var>, this function returns a non-negative
integer which is an upper bound on the multiplicity of any block in
any <var>t</var>-(<var>v</var>,<var>k</var>,<var>lambda</var>) 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 <var>0</var> is returned, then this implies
that a <var>t</var>-(<var>v</var>,<var>k</var>,<var>lambda</var>) design does not exist.

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

See also <a href="CHAP002.htm#SSEC001.6">ResolvableTDesignBlockMultiplicityBound</a>.

<pre>
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
</pre>

<a name = "SSEC001.6"></a>
<li><code>ResolvableTDesignBlockMultiplicityBound( </code><var>t</var><code>, </code><var>v</var><code>, </code><var>k</var><code>, </code><var>lambda</var><code> )</code>

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 <var>t</var>, and positive integers <var>v</var>, <var>k</var> and
<var>lambda</var>, with <var><var>t</var>le<var>k</var>le<var>v</var></var>, this function returns a non-negative
integer which is an upper bound on the multiplicity of any block in any
resolvable <var>t</var>-(<var>v</var>,<var>k</var>,<var>lambda</var>) 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 <var>0</var> is returned, then this implies
that a resolvable <var>t</var>-(<var>v</var>,<var>k</var>,<var>lambda</var>) design does not exist.

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

See also <a href="CHAP002.htm#SSEC001.5">TDesignBlockMultiplicityBound</a>.

<pre>
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
</pre>


<h2><a name="SECT002">2.2 Information from (mixed) orthogonal array parameters</a></h2>

For integers <var>N,k,s,t</var>, with <var>N,k>0</var>, <var>s>1</var>, and <var>0letlek</var>,
an orthogonal array indexorthogonal array
OA<var>(N,k,s,t)</var> is an <var>Ntimesk</var> array, in which the entries come from a
set of size <var>s</var> of symbols, with the property that in any <var>Ntimest</var>
subarray, every possible <var>t</var>-tuple of symbols occurs as a row equally
often (which must be <var>N/st</var> times).

For integers <var>N,k1,...,kw,s1,...,sw,t</var>, with
<var>w,N,k1,...,kw>0</var>, <var>s1,...,sw>1</var>, and <var>0letlek:=k1+cdots+kw</var>,
a mixed orthogonal array
<a name = "I1"></a>

OA<var>(N,s1k_1,...,swk_w,t)</var> is an <var>Ntimesk</var>
array, in which the entries in the first
<var>k1</var> columns come from a set of symbols of size <var>s1</var>, the entries
in the next <var>k2</var> columns come from a set of symbols of size <var>s2</var>,
and so on, with the property that in any <var>Ntimest</var> subarray, every
possible <var>t</var>-tuple of symbols occurs as a row equally often.
Clearly, a mixed orthogonal array OA<var>(N,sk,t)</var> is the same thing as an
orthogonal array OA<var>(N,k,s,t)</var>.

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.

<a name = "SSEC002.1"></a>
<li><code>OARunMultiplicityBound( </code><var>N</var><code>, </code><var>k</var><code>, </code><var>s</var><code>, </code><var>t</var><code> )</code>

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

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

If the value <var>0</var> 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 <var>m</var> is achieved; that
is, there may well be no (mixed) orthogonal array with the given
parameters having a run with multiplicity <var>m</var>.

<pre>
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
</pre>


<h2><a name="SECT003">2.3 Block intersection polynomials</a></h2>

In <a href="biblio.htm#CaSo"><cite>CaSo</cite></a>, 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.

<a name = "SSEC003.1"></a>
<li><code>BlockIntersectionPolynomial(</code><var>x</var><code>, </code><var>m</var><code>, </code><var>lambdavec</var><code> )</code>

For <var>k</var> a non-negative integer, define the polynomial
<var>P(x,k)=x(x-1)cdots(x-k+1)</var>. Let <var>s</var> and <var>t</var> be non-negative
integers, with <var>sget</var>, and let <var>m0,...,ms</var> and
<var>lambda0,...,lambdat</var> be rational numbers. Then the block
intersection polynomial for the sequences <var>[m0,...,ms]</var>,
<var>[lambda0,...,lambdat]</var> is defined to be
<var>sumj=0ttchoosejP(-x,t-j)[P(s,j)lambdaj-sumi=js P(i,j)mi],</var>
and is denoted by <var>B(x,[m0,...,ms],[lambda0,...,lambdat]).</var>

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

The importance of a block intersection polynomial is as follows.
Let <var>D=(V,calB)</var> be a block design, let <var>SsubseteqV</var>, with <var>s=|S|</var>,
and for <var>i=0,...,s</var>, suppose that <var>mi</var> is a non-negative integer
with <var>mileni</var>, where <var>ni</var> is the number of blocks intersecting <var>S</var>
in exactly <var>i</var> points. Let <var>t</var> be a non-negative even integer with <var>tle
s</var>, and suppose that, for <var>j=0...,t</var>, we have <var>lambdaj=1/schoose
jsumTsubseteqS,|T|=jlambdaT</var>, where <var>lambdaT</var> is the
number of blocks of <var>D</var> containing <var>T</var>. Then the block intersection
polynomial <var>B(x)=B(x,[m0,...,ms],[lambda0,...,lambdat])</var>
is a polynomial with integer coefficients, and <var>B(n)ge0</var> for every
integer <var>n</var>. (These conditions can be checked using the function
<a href="CHAP002.htm#SSEC003.2">BlockIntersectionPolynomialCheck</a>.) In addition, if <var>B(n)=0</var> for some
integer <var>n</var>, then <var>mi=ni</var> for <var>inotin{n,n+1,...,n+t-1}</var>.

For more information on block intersection polynomials and their
applications, see <a href="biblio.htm#CaSo"><cite>CaSo</cite></a> and <a href="biblio.htm#Soi10"><cite>Soi10</cite></a>.

<pre>
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
</pre>

<a name = "SSEC003.2"></a>
<li><code>BlockIntersectionPolynomialCheck(</code><var>m</var><code>, </code><var>lambdavec</var><code>)</code>

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

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

See also <a href="CHAP002.htm#SSEC003.1">BlockIntersectionPolynomial</a>.

<pre>
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
</pre>

[<a href = "chapters.htm">Up</a>] [<a href ="CHAP001.htm">Previous</a>] [<a href ="CHAP003.htm">Next</a>] [<a href = "theindex.htm">Index</a>]

<address>design manual November 2024
</address></body></html>

quality100%

Quellcode-Bibliothek CHAP002.htm Sprache: unbekannt

[ Konzepte0.72Was zu einem Entwurf gehört Wie die Entwicklung von Software durchgeführt wird ]