<html><head><title>[design] 2 Information from block 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 block design parameters</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP002.htm#SECT001">Information from $t$-design parameters</a>
<li> <A HREF="CHAP002.htm#SECT002">Block intersection polynomials</a>
</ol><p>
<p>
<p>
<h2><a name="SECT001">2.1 Information from $t$-design parameters</a></h2>
<p><p>
For <var>t</var> a non-negative integer and <var>v,k,lambda</var> positive integers with
<var>tleklev</var>, a <var>t</var>-<strong>design</strong> with <strong>parameters</strong> <var>t,v,k,lambda</var>, or a
<var>t</var>-<var>(v,k,lambda)</var> <strong>design</strong>, 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.
<p>
<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>
<p>
A <var>t</var>-<var>(v,k,lambda)</var> design is also an <var>s</var>-<var>(v,k,lambda<sub>s</sub>)</var> design
for <var>0leslet</var>, where <var>lambda<sub>s</sub>=lambdav-s chooset-s/k-s
chooset-s</var>.
<p>
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>lambda<sub>s</sub></var> as defined above,
if all the <var>lambda<sub>s</sub></var> are integers. Otherwise, <code>fail</code> is returned.
<p>
<pre>
gap> TDesignLambdas(5,24,8,1);
[ 759, 253, 77, 21, 5, 1 ]
</pre>
<p>
<a name = "SSEC001.2"></a>
<li><code>TDesignLambdaMin( </code><var>t</var><code>, </code><var>v</var><code>, </code><var>k</var><code> )</code>
<p>
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>.
<p>
See <a href="CHAP002.htm#SSEC001.1">TDesignLambdas</a>.
<p>
<pre>
gap> TDesignLambdaMin(5,24,8);
1
gap> TDesignLambdaMin(2,12,4);
3
</pre>
<p>
<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>
<p>
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>-<strong>intersection number</strong> 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>).
<p>
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
<strong><var>t</var>-design intersection triangle</strong>, 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>.
<p>
<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>
<p>
<a name = "SSEC001.4"></a>
<li><code>SteinerSystemIntersectionTriangle( </code><var>t</var><code>, </code><var>v</var><code>, </code><var>k</var><code> )</code>
<p>
A <strong>Steiner system</strong> 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>.
<p>
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>-<strong>intersection number</strong> 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.
<p>
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 <strong>Steiner
system intersection triangle</strong>, 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.
<p>
See also <a href="CHAP002.htm#SSEC001.3">TDesignIntersectionTriangle</a>.
<p>
<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>
<p>
<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>
<p>
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 <strong>multiplicity</strong> 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.
<p>
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>.
<p>
See also <a href="CHAP002.htm#SSEC001.6">ResolvableTDesignBlockMultiplicityBound</a>.
<p>
<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>
<p>
<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>
<p>
A <strong>resolution</strong> 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 <strong>resolvable</strong> if it has a resolution.
<p>
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 <strong>multiplicity</strong> 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.
<p>
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>.
<p>
See also <a href="CHAP002.htm#SSEC001.5">TDesignBlockMultiplicityBound</a>.
<p>
<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>
<p>
<p>
<h2><a name="SECT002">2.2 Block intersection polynomials</a></h2>
<p><p>
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.
<p>
<a name = "SSEC002.1"></a>
<li><code>BlockIntersectionPolynomial(</code><var>x</var><code>, </code><var>m</var><code>, </code><var>lambdavec</var><code> )</code>
<p>
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>m<sub>0</sub>,...,m<sub>s</sub></var> and
<var>lambda<sub>0</sub>,...,lambda<sub>t</sub></var> be rational numbers. Then the <strong>block
intersection polynomial</strong> for the sequences <var>[m<sub>0</sub>,...,m<sub>s</sub>]</var>,
<var>[lambda<sub>0</sub>,...,lambda<sub>t</sub>]</var> is defined to be
<p><var>sum<sub>j=0</sub><sup>t</sup>tchoosejP(-x,t-j)[P(s,j)lambda<sub>j</sub>-sum<sub>i=j</sub><sup>s</sup> P(i,j)m<sub>i</sub>],<p></var>
and is denoted by <var>B(x,[m<sub>0</sub>,...,m<sub>s</sub>],[lambda<sub>0</sub>,...,lambda<sub>t</sub>]).</var>
<p>
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>.
<p>
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>m<sub>i</sub></var> is a non-negative integer
with <var>m<sub>i</sub>len<sub>i</sub></var>, where <var>n<sub>i</sub></var> is the number of blocks intersecting <var>S</var>
in exactly <var>i</var> points. Let <var>t</var> be a non-negative <strong>even</strong> integer with <var>tle
s</var>, and suppose that, for <var>j=0...,t</var>, we have <var>lambda<sub>j</sub>=1/schoose
jsum<sub>TsubseteqS,|T|=j</sub>lambda<sub>T</sub></var>, where <var>lambda<sub>T</sub></var> is the
number of blocks of <var>D</var> containing <var>T</var>. Then the block intersection
polynomial <var>B(x)=B(x,[m<sub>0</sub>,...,m<sub>s</sub>],[lambda<sub>0</sub>,...,lambda<sub>t</sub>])</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#SSEC002.2">BlockIntersectionPolynomialCheck</a>.) In addition, if <var>B(n)=0</var> for some
integer <var>n</var>, then <var>m<sub>i</sub>=n<sub>i</sub></var> for <var>inotin{n,n+1,...,n+t-1}</var>.
<p>
For more information on block intersection polynomials and their
applications, see <a href="biblio.htm#CaSo"><cite>CaSo</cite></a>.
<p>
<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>
<p>
<a name = "SSEC002.2"></a>
<li><code>BlockIntersectionPolynomialCheck(</code><var>m</var><code>, </code><var>lambdavec</var><code>)</code>
<p>
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>.
<p>
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.
<p>
See also <a href="CHAP002.htm#SSEC002.1">BlockIntersectionPolynomial</a>.
<p>
<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>
<p>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP001.htm">Previous</a>] [<a href ="CHAP003.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>design manual<br>November 2006
</address></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
938
