<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (guava) - Chapter 7:
Bounds on codes, special matrices and miscellaneous functions
</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap6.html">Previous Chapter</a> <a href="chapBib.html">Next Chapter</a> </div>
<p><a id="X7A814D518460862E" name="X7A814D518460862E"></a></p>
<div class="ChapSects"><a href="chap7.html#X7A814D518460862E">7. <span class="Heading">
Bounds on codes, special matrices and miscellaneous functions
</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X87C753EB840C34D3">7.1 <span class="Heading">
Distance bounds on codes
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8673277C7F6C04C3">7.1-1 UpperBoundSingleton</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X828095537C91FDFA">7.1-2 UpperBoundHamming</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X82EBFAAB7F5BFD4A">7.1-3 UpperBoundJohnson</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A26E2537DFF4409">7.1-4 UpperBoundPlotkin</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X86A5A7C67F625A40">7.1-5 UpperBoundElias</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X82366C277E218130">7.1-6 UpperBoundGriesmer</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8301FA9F7C6C7445">7.1-7 IsGriesmerCode</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A5CB74485184FEE">7.1-8 UpperBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7FDF54BA81115D88">7.1-9 LowerBoundMinimumDistance</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7CF15D2084499869">7.1-10 LowerBoundGilbertVarshamov</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8217D830871286D8">7.1-11 LowerBoundSpherePacking</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C6A58327BD6B685">7.1-12 UpperBoundMinimumDistance</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B3858B27A9E509A">7.1-13 BoundsMinimumDistance</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X817D0A647D3331EB">7.2 <span class="Heading">
Covering radius bounds on codes
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8320D1C180A1AAAD">7.2-1 BoundsCoveringRadius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7881E03E812140F4">7.2-2 IncreaseCoveringRadiusLowerBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7AD9F1D27C52BC0F">7.2-3 ExhaustiveSearchCoveringRadius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X85D671F4824B4B0C">7.2-4 GeneralLowerBoundCoveringRadius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8638F5A67D6E50C1">7.2-5 GeneralUpperBoundCoveringRadius</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7E7FBCC87D5562AB">7.2-6 LowerBoundCoveringRadiusSphereCovering</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X85E20C518360AB70">7.2-7 LowerBoundCoveringRadiusVanWee1</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C72994A825228E7">7.2-8 LowerBoundCoveringRadiusVanWee2</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7F95362485759ACB">7.2-9 LowerBoundCoveringRadiusCountingExcess</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X829C14A383B5BF59">7.2-10 LowerBoundCoveringRadiusEmbedded1</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B0C81B88604C448">7.2-11 LowerBoundCoveringRadiusEmbedded2</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7D27F6E27B9A0D35">7.2-12 LowerBoundCoveringRadiusInduction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80F8DFAD7D67CBEC">7.2-13 UpperBoundCoveringRadiusRedundancy</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X832847A17FD0D142">7.2-14 UpperBoundCoveringRadiusDelsarte</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X86F10D9E79AB8796">7.2-15 UpperBoundCoveringRadiusStrength</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8585C6A982489FC3">7.2-16 UpperBoundCoveringRadiusGriesmerLike</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X82A38F5F858CF3FC">7.2-17 UpperBoundCoveringRadiusCyclicCode</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X806EBEC77C16E657">7.3 <span class="Heading">
Special matrices in <strong class="pkg">GUAVA</strong>
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X82899B64802A4BCE">7.3-1 KrawtchoukMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X87AFE2C078031CE4">7.3-2 GrayMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7E1E7C5287919CDB">7.3-3 SylvesterMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8014A1F181ECD8AA">7.3-4 HadamardMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X797F43607AD8660D">7.3-5 VandermondeMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B47D82485B66F1D">7.3-6 PutStandardForm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7D4EDA0A854EBFEF">7.3-7 IsInStandardForm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A97AD477E7638DE">7.3-8 PermutedCols</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B68119F85E9EC6D">7.3-9 VerticalConversionFieldMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8033E9A67BA155C8">7.3-10 HorizontalConversionFieldMat</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X804AAFF2867080F7">7.3-11 MOLS</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7F34306B81DC2776">7.3-12 IsLatinSquare</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X81B9B40B7B2D97D5">7.3-13 AreMOLS</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X7AB5E5CE7FDF7132">7.4 <span class="Heading">
Some functions related to the norm of a code
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8032E53078264ABB">7.4-1 CoordinateNorm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7ED2EF368203AF47">7.4-2 CodeNorm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7D24F8BF7F9A7BF1">7.4-3 IsCoordinateAcceptable</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X87039FD179AD3009">7.4-4 GeneralizedCodeNorm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80283A2F7C8101BD">7.4-5 IsNormalCode</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X8308D685809A4E2F">7.5 <span class="Heading">
Miscellaneous functions
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X871286437DE7A6A4">7.5-1 CodeWeightEnumerator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X84DA928083B103A0">7.5-2 CodeDistanceEnumerator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X84B2BE66780EFBF9">7.5-3 CodeMacWilliamsTransform</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7903286078F8051B">7.5-4 CodeDensity</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X85303BAE7BD46D81">7.5-5 SphereContent</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7ACDC5377CD17451">7.5-6 Krawtchouk</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X827E39957A87EB51">7.5-7 PrimitiveUnityRoot</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X78AEA40F7AD9D541">7.5-8 PrimitivePolynomialsNr</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A2B54EF868AA752">7.5-9 IrreduciblePolynomialsNr</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7B50D3417F6FD7C6">7.5-10 MatrixRepresentationOfElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7805D2BB7CE4D455">7.5-11 ReciprocalPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7AEA9F807E6FFEFF">7.5-12 CyclotomicCosets</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7A4EA98D794CF410">7.5-13 WeightHistogram</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X805DF25C84585FD6">7.5-14 MultiplicityInList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8072B0DA78FBE562">7.5-15 MostCommonInList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C5407EF87849857">7.5-16 RotateList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X85E526367878F72A">7.5-17 CirculantMatrix</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X7969103F7A8598F9">7.6 <span class="Heading">
Miscellaneous polynomial functions
</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X84D51EBB784E7C5D">7.6-1 MatrixTransformationOnMultivariatePolynomial </a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80433A4B792880EF">7.6-2 DegreeMultivariatePolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X83F44E397C56F2E0">7.6-3 DegreesMultivariatePolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7E9021697A61A60F">7.6-4 CoefficientMultivariatePolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X79E76B6F7D177E27">7.6-5 SolveLinearSystem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X80171AA687FFDC70">7.6-6 GuavaVersion</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7EBBE86D85CC90C0">7.6-7 ZechLog</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X7C8C1E6A7E3497F0">7.6-8 CoefficientToPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X8431985183B63BB7">7.6-9 DegreesMonomialTerm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7.html#X860EF39B841380A1">7.6-10 DivisorsMultivariatePolynomial</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap7.html#X82257DE97D1822AA">7.7 <span class="Heading">
GNU Free Documentation License
</span></a>
</div>
</div>
<h3>7. <span class="Heading">
Bounds on codes, special matrices and miscellaneous functions
</span></h3>
<p>In this chapter we describe functions that determine bounds on the size and minimum distance of codes (Section <a href="chap7.html#X87C753EB840C34D3"><b>7.1</b></a>), functions that determine bounds on the size and covering radius of codes (Section <a href="chap7.html#X817D0A647D3331EB"><b>7.2</b></a>), functions that work with special matrices <strong class="pkg">GUAVA</strong> needs for several codes (see Section <a href="chap7.html#X806EBEC77C16E657"><b>7.3</b></a>), and constructing codes or performing calculations with codes (see Section <a href="chap7.html#X8308D685809A4E2F"><b>7.5</b></a>).</p>
<p><a id="X87C753EB840C34D3" name="X87C753EB840C34D3"></a></p>
<h4>7.1 <span class="Heading">
Distance bounds on codes
</span></h4>
<p>This section describes the functions that calculate estimates for upper bounds on the size and minimum distance of codes. Several algorithms are known to compute a largest number of words a code can have with given length and minimum distance. It is important however to understand that in some cases the true upper bound is unknown. A code which has a size equalto the calculated upper bound may not have been found. However, codes that have a larger size do not exist.</p>
<p>A second way to obtain bounds is a table. In <strong class="pkg">GUAVA</strong>, an extensive table is implemented for linear codes over GF(2), GF(3) and GF(4). It contains bounds on the minimum distance for given word length and dimension. It contains entries for word lengths less than or equal to 257, 243 and 256 for codes over GF(2), GF(3) and GF(4) respectively. These entries were obtained from Brouwer's tables as of 11 May 2006. For the latest information, please see A. E. Brouwer's tables <a href="chapBib.html#biBBr">[Bro06]</a> on the internet.</p>
<p>Firstly, we describe functions that compute specific upper bounds on the code size (see <code class="func">UpperBoundSingleton</code> (<a href="chap7.html#X8673277C7F6C04C3"><b>7.1-1</b></a>), <code class="func">UpperBoundHamming</code> (<a href="chap7.html#X828095537C91FDFA"><b>7.1-2</b></a>), <code class="func">UpperBoundJohnson</code> (<a href="chap7.html#X82EBFAAB7F5BFD4A"><b>7.1-3</b></a>), <code class="func">UpperBoundPlotkin</code> (<a href="chap7.html#X7A26E2537DFF4409"><b>7.1-4</b></a>), <code class="func">UpperBoundElias</code> (<a href="chap7.html#X86A5A7C67F625A40"><b>7.1-5</b></a>) and <code class="func">UpperBoundGriesmer</code> (<a href="chap7.html#X82366C277E218130"><b>7.1-6</b></a>)).</p>
<p>Next we describe a function that computes <strong class="pkg">GUAVA</strong>'s best upper bound on the code size (see <code class="func">UpperBound</code> (<a href="chap7.html#X7A5CB74485184FEE"><b>7.1-8</b></a>)).</p>
<p>Then we describe two functions that compute a lower and upper bound on the minimum distance of a code (see <code class="func">LowerBoundMinimumDistance</code> (<a href="chap7.html#X7FDF54BA81115D88"><b>7.1-9</b></a>) and <code class="func">UpperBoundMinimumDistance</code> (<a href="chap7.html#X7C6A58327BD6B685"><b>7.1-12</b></a>)).</p>
<p>Finally, we describe a function that returns a lower and upper bound on the minimum distance with given parameters and a description of how the bounds were obtained (see <code class="func">BoundsMinimumDistance</code> (<a href="chap7.html#X7B3858B27A9E509A"><b>7.1-13</b></a>)).</p>
<p><a id="X8673277C7F6C04C3" name="X8673277C7F6C04C3"></a></p>
<h5>7.1-1 UpperBoundSingleton</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundSingleton</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">UpperBoundSingleton</code> returns the Singleton bound for a code of length <var class="Arg">n</var>, minimum distance <var class="Arg">d</var> over a field of size <var class="Arg">q</var>. This bound is based on the shortening of codes. By shortening an (n, M, d) code d-1 times, an (n-d+1,M,1) code results, with M <= q^n-d+1 (see <code class="func">ShortenedCode</code> (<a href="chap6.html#X81CBEAFF7B9DE6EF"><b>6.1-9</b></a>)). Thus</p>
<p class="pcenter">
M \leq q^{n-d+1}.
</p>
<p>Codes that meet this bound are called <em>maximum distance separable</em> (see <code class="func">IsMDSCode</code> (<a href="chap4.html#X789380D28018EC3F"><b>4.3-7</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundSingleton(4, 3, 5);
25
gap> C := ReedSolomonCode(4,3);; Size(C);
25
gap> IsMDSCode(C);
true
</pre></td></tr></table>
<p><a id="X828095537C91FDFA" name="X828095537C91FDFA"></a></p>
<h5>7.1-2 UpperBoundHamming</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundHamming</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The Hamming bound (also known as the <em>sphere packing bound</em>) returns an upper bound on the size of a code of length <var class="Arg">n</var>, minimum distance <var class="Arg">d</var>, over a field of size <var class="Arg">q</var>. The Hamming bound is obtained by dividing the contents of the entire space GF(q)^n by the contents of a ball with radius lfloor(d-1) / 2rfloor. As all these balls are disjoint, they can never contain more than the whole vector space.</p>
<p class="pcenter">
M \leq {q^n \over V(n,e)},
</p>
<p>where M is the maxmimum number of codewords and V(n,e) is equal to the contents of a ball of radius e (see <code class="func">SphereContent</code> (<a href="chap7.html#X85303BAE7BD46D81"><b>7.5-5</b></a>)). This bound is useful for small values of <var class="Arg">d</var>. Codes for which equality holds are called <em>perfect</em> (see <code class="func">IsPerfectCode</code> (<a href="chap4.html#X85E3BD26856424F7"><b>4.3-6</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundHamming( 15, 3, 2 );
2048
gap> C := HammingCode( 4, GF(2) );
a linear [15,11,3]1 Hamming (4,2) code over GF(2)
gap> Size( C );
2048
</pre></td></tr></table>
<p><a id="X82EBFAAB7F5BFD4A" name="X82EBFAAB7F5BFD4A"></a></p>
<h5>7.1-3 UpperBoundJohnson</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundJohnson</code>( <var class="Arg">n, d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The Johnson bound is an improved version of the Hamming bound (see <code class="func">UpperBoundHamming</code> (<a href="chap7.html#X828095537C91FDFA"><b>7.1-2</b></a>)). In addition to the Hamming bound, it takes into account the elements of the space outside the balls of radius e around the elements of the code. The Johnson bound only works for binary codes.</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundJohnson( 13, 5 );
77
gap> UpperBoundHamming( 13, 5, 2);
89 # in this case the Johnson bound is better
</pre></td></tr></table>
<p><a id="X7A26E2537DFF4409" name="X7A26E2537DFF4409"></a></p>
<h5>7.1-4 UpperBoundPlotkin</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundPlotkin</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">UpperBoundPlotkin</code> calculates the sum of the distances of all ordered pairs of different codewords. It is based on the fact that the minimum distance is at most equal to the average distance. It is a good bound if the weights of the codewords do not differ much. It results in:</p>
<p class="pcenter">
M \leq {d \over {d-(1-1/q)n}},
</p>
<p>where M is the maximum number of codewords. In this case, <var class="Arg">d</var> must be larger than (1-1/q)n, but by shortening the code, the case d < (1-1/q)n is covered.</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundPlotkin( 15, 7, 2 );
32
gap> C := BCHCode( 15, 7, GF(2) );
a cyclic [15,5,7]5 BCH code, delta=7, b=1 over GF(2)
gap> Size(C);
32
gap> WeightDistribution(C);
[ 1, 0, 0, 0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 1 ]
</pre></td></tr></table>
<p><a id="X86A5A7C67F625A40" name="X86A5A7C67F625A40"></a></p>
<h5>7.1-5 UpperBoundElias</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundElias</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The Elias bound is an improvement of the Plotkin bound (see <code class="func">UpperBoundPlotkin</code> (<a href="chap7.html#X7A26E2537DFF4409"><b>7.1-4</b></a>)) for large codes. Subcodes are used to decrease the size of the code, in this case the subcode of all codewords within a certain ball. This bound is useful for large codes with relatively small minimum distances.</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundPlotkin( 16, 3, 2 );
12288
gap> UpperBoundElias( 16, 3, 2 );
10280
gap> UpperBoundElias( 20, 10, 3 );
16255
</pre></td></tr></table>
<p><a id="X82366C277E218130" name="X82366C277E218130"></a></p>
<h5>7.1-6 UpperBoundGriesmer</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundGriesmer</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The Griesmer bound is valid only for linear codes. It is obtained by counting the number of equal symbols in each row of the generator matrix of the code. By omitting the coordinates in which all rows have a zero, a smaller code results. The Griesmer bound is obtained by repeating this proces until a trivial code is left in the end.</p>
<table class="example">
<tr><td><pre>
gap> UpperBoundGriesmer( 13, 5, 2 );
64
gap> UpperBoundGriesmer( 18, 9, 2 );
8 # the maximum number of words for a linear code is 8
gap> Size( PuncturedCode( HadamardCode( 20, 1 ) ) );
20 # this non-linear code has 20 elements
</pre></td></tr></table>
<p><a id="X8301FA9F7C6C7445" name="X8301FA9F7C6C7445"></a></p>
<h5>7.1-7 IsGriesmerCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsGriesmerCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsGriesmerCode</code> returns `true' if a linear code <var class="Arg">C</var> is a Griesmer code, and `false' otherwise. A code is called <em>Griesmer</em> if its length satisfies</p>
<p class="pcenter">
n = g[k,d] = \sum_{i=0}^{k-1} \lceil \frac{d}{q^i} \rceil.
</p>
<table class="example">
<tr><td><pre>
gap> IsGriesmerCode( HammingCode( 3, GF(2) ) );
true
gap> IsGriesmerCode( BCHCode( 17, 2, GF(2) ) );
false
</pre></td></tr></table>
<p><a id="X7A5CB74485184FEE" name="X7A5CB74485184FEE"></a></p>
<h5>7.1-8 UpperBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBound</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">UpperBound</code> returns the best known upper bound A(n,d) for the size of a code of length <var class="Arg">n</var>, minimum distance <var class="Arg">d</var> over a field of size <var class="Arg">q</var>. The function <code class="code">UpperBound</code> first checks for trivial cases (like d=1 or n=d), and if the value is in the built-in table. Then it calculates the minimum value of the upper bound using the methods of Singleton (see <code class="func">UpperBoundSingleton</code> (<a href="chap7.html#X8673277C7F6C04C3"><b>7.1-1</b></a>)), Hamming (see <code class="func">UpperBoundHamming</code> (<a href="chap7.html#X828095537C91FDFA"><b>7.1-2</b></a>)), Johnson (see <code class="func">UpperBoundJohnson</code> (<a href="chap7.html#X82EBFAAB7F5BFD4A"><b>7.1-3</b></a>)), Plotkin (see <code class="func">UpperBoundPlotkin</code> (<a href="chap7.html#X7A26E2537DFF4409"><b>7.1-4</b></a>)) and Elias (see <code class="func">UpperBoundElias</code> (<a href="chap7.html#X86A5A7C67F625A40"><b>7.1-5</b></a>)). If the code is binary, A(n, 2* ell-1) = A(n+1,2* ell), so the <code class="code">UpperBound</code> takes the minimum of the values obtained from all methods for the parameters (n, 2*ell-1) and (n+1, 2* ell).</p>
<table class="example">
<tr><td><pre>
gap> UpperBound( 10, 3, 2 );
85
gap> UpperBound( 25, 9, 8 );
1211778792827540
</pre></td></tr></table>
<p><a id="X7FDF54BA81115D88" name="X7FDF54BA81115D88"></a></p>
<h5>7.1-9 LowerBoundMinimumDistance</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundMinimumDistance</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In this form, <code class="code">LowerBoundMinimumDistance</code> returns a lower bound for the minimum distance of code <var class="Arg">C</var>.</p>
<p>This command can also be called using the syntax <code class="code">LowerBoundMinimumDistance( n, k, F )</code>. In this form, <code class="code">LowerBoundMinimumDistance</code> returns a lower bound for the minimum distance of the best known linear code of length <var class="Arg">n</var>, dimension <var class="Arg">k</var> over field <var class="Arg">F</var>. It uses the mechanism explained in section <a href="chap7.html#X7B3858B27A9E509A"><b>7.1-13</b></a>.</p>
<table class="example">
<tr><td><pre>
gap> C := BCHCode( 45, 7 );
a cyclic [45,23,7..9]6..16 BCH code, delta=7, b=1 over GF(2)
gap> LowerBoundMinimumDistance( C );
7 # designed distance is lower bound for minimum distance
gap> LowerBoundMinimumDistance( 45, 23, GF(2) );
10
</pre></td></tr></table>
<p><a id="X7CF15D2084499869" name="X7CF15D2084499869"></a></p>
<h5>7.1-10 LowerBoundGilbertVarshamov</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundGilbertVarshamov</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is the lower bound due (independently) to Gilbert and Varshamov. It says that for each <var class="Arg">n</var> and <var class="Arg">d</var>, there exists a linear code having length n and minimum distance d at least of size q^n-1/ SphereContent(n-1,d-2,GF(q)).</p>
<table class="example">
<tr><td><pre>
gap> LowerBoundGilbertVarshamov(3,2,2);
4
gap> LowerBoundGilbertVarshamov(3,3,2);
1
gap> LowerBoundMinimumDistance(3,3,2);
1
gap> LowerBoundMinimumDistance(3,2,2);
2
</pre></td></tr></table>
<p><a id="X8217D830871286D8" name="X8217D830871286D8"></a></p>
<h5>7.1-11 LowerBoundSpherePacking</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundSpherePacking</code>( <var class="Arg">n, d, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is the lower bound due (independently) to Gilbert and Varshamov. It says that for each <var class="Arg">n</var> and <var class="Arg">r</var>, there exists an unrestricted code at least of size q^n/ SphereContent(n,d,GF(q)) minimum distance d.</p>
<table class="example">
<tr><td><pre>
gap> LowerBoundSpherePacking(3,2,2);
2
gap> LowerBoundSpherePacking(3,3,2);
1
</pre></td></tr></table>
<p><a id="X7C6A58327BD6B685" name="X7C6A58327BD6B685"></a></p>
<h5>7.1-12 UpperBoundMinimumDistance</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundMinimumDistance</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>In this form, <code class="code">UpperBoundMinimumDistance</code> returns an upper bound for the minimum distance of code <var class="Arg">C</var>. For unrestricted codes, it just returns the word length. For linear codes, it takes the minimum of the possibly known value from the method of construction, the weight of the generators, and the value from the table (see <a href="chap7.html#X7B3858B27A9E509A"><b>7.1-13</b></a>).</p>
<p>This command can also be called using the syntax <code class="code">UpperBoundMinimumDistance( n, k, F )</code>. In this form, <code class="code">UpperBoundMinimumDistance</code> returns an upper bound for the minimum distance of the best known linear code of length <var class="Arg">n</var>, dimension <var class="Arg">k</var> over field <var class="Arg">F</var>. It uses the mechanism explained in section <a href="chap7.html#X7B3858B27A9E509A"><b>7.1-13</b></a>.</p>
<table class="example">
<tr><td><pre>
gap> C := BCHCode( 45, 7 );;
gap> UpperBoundMinimumDistance( C );
9
gap> UpperBoundMinimumDistance( 45, 23, GF(2) );
11
</pre></td></tr></table>
<p><a id="X7B3858B27A9E509A" name="X7B3858B27A9E509A"></a></p>
<h5>7.1-13 BoundsMinimumDistance</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BoundsMinimumDistance</code>( <var class="Arg">n, k, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">BoundsMinimumDistance</code> calculates a lower and upper bound for the minimum distance of an optimal linear code with word length <var class="Arg">n</var>, dimension <var class="Arg">k</var> over field <var class="Arg">F</var>. The function returns a record with the two bounds and an explanation for each bound. The function <code class="code">Display</code> can be used to show the explanations.</p>
<p>The values for the lower and upper bound are obtained from a table. <strong class="pkg">GUAVA</strong> has tables containing lower and upper bounds for q=2 (n <= 257), 3 (n <= 243), 4 (n <= 256). (Current as of 11 May 2006.) These tables were derived from the table of Brouwer. (See <a href="chapBib.html#biBBr">[Bro06]</a>, <span class="URL"><a href="http://www.win.tue.nl/~aeb/voorlincod.html">http://www.win.tue.nl/~aeb/voorlincod.html</a></span> for the most recent data.) For codes over other fields and for larger word lengths, trivial bounds are used.</p>
<p>The resulting record can be used in the function <code class="code">BestKnownLinearCode</code> (see <code class="func">BestKnownLinearCode</code> (<a href="chap5.html#X871508567CB34D96"><b>5.2-14</b></a>)) to construct a code with minimum distance equal to the lower bound.</p>
<table class="example">
<tr><td><pre>
gap> bounds := BoundsMinimumDistance( 7, 3 );; DisplayBoundsInfo( bounds );
an optimal linear [7,3,d] code over GF(2) has d=4
------------------------------------------------------------------------------
Lb(7,3)=4, by shortening of:
Lb(8,4)=4, u u+v construction of C1 and C2:
Lb(4,3)=2, dual of the repetition code
Lb(4,1)=4, repetition code
------------------------------------------------------------------------------
Ub(7,3)=4, Griesmer bound
# The lower bound is equal to the upper bound, so a code with
# these parameters is optimal.
gap> C := BestKnownLinearCode( bounds );; Display( C );
a linear [7,3,4]2..3 shortened code of
a linear [8,4,4]2 U U+V construction code of
U: a cyclic [4,3,2]1 dual code of
a cyclic [4,1,4]2 repetition code over GF(2)
V: a cyclic [4,1,4]2 repetition code over GF(2)
</pre></td></tr></table>
<p><a id="X817D0A647D3331EB" name="X817D0A647D3331EB"></a></p>
<h4>7.2 <span class="Heading">
Covering radius bounds on codes
</span></h4>
<p><a id="X8320D1C180A1AAAD" name="X8320D1C180A1AAAD"></a></p>
<h5>7.2-1 BoundsCoveringRadius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BoundsCoveringRadius</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">BoundsCoveringRadius</code> returns a list of integers. The first entry of this list is the maximum of some lower bounds for the covering radius of <var class="Arg">C</var>, the last entry the minimum of some upper bounds of <var class="Arg">C</var>.</p>
<p>If the covering radius of <var class="Arg">C</var> is known, a list of length 1 is returned. <code class="code">BoundsCoveringRadius</code> makes use of the functions <code class="code">GeneralLowerBoundCoveringRadius</code> and <code class="code">GeneralUpperBoundCoveringRadius</code>.</p>
<table class="example">
<tr><td><pre>
gap> BoundsCoveringRadius( BCHCode( 17, 3, GF(2) ) );
[ 3 .. 4 ]
gap> BoundsCoveringRadius( HammingCode( 5, GF(2) ) );
[ 1 ]
</pre></td></tr></table>
<p><a id="X7881E03E812140F4" name="X7881E03E812140F4"></a></p>
<h5>7.2-2 IncreaseCoveringRadiusLowerBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IncreaseCoveringRadiusLowerBound</code>( <var class="Arg">C[, stopdist][, startword]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IncreaseCoveringRadiusLowerBound</code> tries to increase the lower bound of the covering radius of <var class="Arg">C</var>. It does this by means of a probabilistic algorithm. This algorithm takes a random word in GF(q)^n (or <var class="Arg">startword</var> if it is specified), and, by changing random coordinates, tries to get as far from <var class="Arg">C</var> as possible. If changing a coordinate finds a word that has a larger distance to the code than the previous one, the change is made permanent, and the algorithm starts all over again. If changing a coordinate does not find a coset leader that is further away from the code, then the change is made permanent with a chance of 1 in 100, if it gets the word closer to the code, or with a chance of 1 in 10, if the word stays at the same distance. Otherwise, the algorithm starts again with the same word as before.</p>
<p>If the algorithm did not allow changes that decrease the distance to the code, it might get stuck in a sub-optimal situation (the coset leader corresponding to such a situation - i.e. no coordinate of this coset leader can be changed in such a way that we get at a larger distance from the code - is called an <em>orphan</em>).</p>
<p>If the algorithm finds a word that has distance <var class="Arg">stopdist</var> to the code, it ends and returns that word, which can be used for further investigations.</p>
<p>The variable <var class="Arg">InfoCoveringRadius</var> can be set to <var class="Arg">Print</var> to print the maximum distance reached so far every 1000 runs. The algorithm can be interrupted with <strong class="button">ctrl-C</strong>, allowing the user to look at the word that is currently being examined (called `current'), or to change the chances that the new word is made permanent (these are called `staychance' and `downchance'). If one of these variables is i, then it corresponds with a i in 100 chance.</p>
<p>At the moment, the algorithm is only useful for codes with small dimension, where small means that the elements of the code fit in the memory. It works with larger codes, however, but when you use it for codes with large dimension, you should be <em>very</em> patient. If running the algorithm quits GAP (due to memory problems), you can change the global variable <var class="Arg">CRMemSize</var> to a lower value. This might cause the algorithm to run slower, but without quitting GAP. The only way to find out the best value of <var class="Arg">CRMemSize</var> is by experimenting.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> IncreaseCoveringRadiusLowerBound(C,10);
Number of runs: 1000 best distance so far: 3
Number of runs: 2000 best distance so far: 3
Number of changes: 100
Number of runs: 3000 best distance so far: 3
Number of runs: 4000 best distance so far: 3
Number of runs: 5000 best distance so far: 3
Number of runs: 6000 best distance so far: 3
Number of runs: 7000 best distance so far: 3
Number of changes: 200
Number of runs: 8000 best distance so far: 3
Number of runs: 9000 best distance so far: 3
Number of runs: 10000 best distance so far: 3
Number of changes: 300
Number of runs: 11000 best distance so far: 3
Number of runs: 12000 best distance so far: 3
Number of runs: 13000 best distance so far: 3
Number of changes: 400
Number of runs: 14000 best distance so far: 3
user interrupt at...
#
# used ctrl-c to break out of execution
#
... called from
IncreaseCoveringRadiusLowerBound( code, -1, current ) called from
function( arguments ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> current;
[ Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ]
brk>
gap> CoveringRadius(C);
3
</pre></td></tr></table>
<p><a id="X7AD9F1D27C52BC0F" name="X7AD9F1D27C52BC0F"></a></p>
<h5>7.2-3 ExhaustiveSearchCoveringRadius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ExhaustiveSearchCoveringRadius</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">ExhaustiveSearchCoveringRadius</code> does an exhaustive search to find the covering radius of <var class="Arg">C</var>. Every time a coset leader of a coset with weight w is found, the function tries to find a coset leader of a coset with weight w+1. It does this by enumerating all words of weight w+1, and checking whether a word is a coset leader. The start weight is the current known lower bound on the covering radius.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> ExhaustiveSearchCoveringRadius(C);
Trying 3 ...
[ 3 .. 5 ]
gap> CoveringRadius(C);
3
</pre></td></tr></table>
<p><a id="X85D671F4824B4B0C" name="X85D671F4824B4B0C"></a></p>
<h5>7.2-4 GeneralLowerBoundCoveringRadius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneralLowerBoundCoveringRadius</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GeneralLowerBoundCoveringRadius</code> returns a lower bound on the covering radius of <var class="Arg">C</var>. It uses as many functions which names start with <code class="code">LowerBoundCoveringRadius</code> as possible to find the best known lower bound (at least that <strong class="pkg">GUAVA</strong> knows of) together with tables for the covering radius of binary linear codes with length not greater than 64.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> GeneralLowerBoundCoveringRadius(C);
2
gap> CoveringRadius(C);
3
</pre></td></tr></table>
<p><a id="X8638F5A67D6E50C1" name="X8638F5A67D6E50C1"></a></p>
<h5>7.2-5 GeneralUpperBoundCoveringRadius</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneralUpperBoundCoveringRadius</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GeneralUpperBoundCoveringRadius</code> returns an upper bound on the covering radius of <var class="Arg">C</var>. It uses as many functions which names start with <code class="code">UpperBoundCoveringRadius</code> as possible to find the best known upper bound (at least that <strong class="pkg">GUAVA</strong> knows of).</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> GeneralUpperBoundCoveringRadius(C);
4
gap> CoveringRadius(C);
3
</pre></td></tr></table>
<p><a id="X7E7FBCC87D5562AB" name="X7E7FBCC87D5562AB"></a></p>
<h5>7.2-6 LowerBoundCoveringRadiusSphereCovering</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusSphereCovering</code>( <var class="Arg">n, M[, F], false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called using the syntax <code class="code">LowerBoundCoveringRadiusSphereCovering( n, r, [F,] true )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusSphereCovering</code> is <var class="Arg">false</var>, then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p><var class="Arg">F</var> is the field over which the code is defined. If <var class="Arg">F</var> is omitted, it is assumed that the code is over GF(2). The bound is computed according to the sphere covering bound:</p>
<p class="pcenter">
M \cdot V_q(n,r) \geq q^n
</p>
<p>where V_q(n,r) is the size of a sphere of radius r in GF(q)^n.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
3
gap> LowerBoundCoveringRadiusSphereCovering(10,32,GF(2),false);
2
gap> LowerBoundCoveringRadiusSphereCovering(10,3,GF(2),true);
6
</pre></td></tr></table>
<p><a id="X85E20C518360AB70" name="X85E20C518360AB70"></a></p>
<h5>7.2-7 LowerBoundCoveringRadiusVanWee1</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusVanWee1</code>( <var class="Arg">n, M[, F], false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called using the syntax <code class="code">LowerBoundCoveringRadiusVanWee1( n, r, [F,] true )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusVanWee1</code> is <var class="Arg">false</var>, then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p><var class="Arg">F</var> is the field over which the code is defined. If <var class="Arg">F</var> is omitted, it is assumed that the code is over GF(2).</p>
<p>The Van Wee bound is an improvement of the sphere covering bound:</p>
<p class="pcenter">
M \cdot \left\{ V_q(n,r) -
\frac{{n \choose r}}{\lceil\frac{n-r}{r+1}\rceil}
\left(\left\lceil\frac{n+1}{r+1}\right\rceil - \frac{n+1}{r+1}\right)
\right\} \geq q^n
</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
3
gap> LowerBoundCoveringRadiusVanWee1(10,32,GF(2),false);
2
gap> LowerBoundCoveringRadiusVanWee1(10,3,GF(2),true);
6
</pre></td></tr></table>
<p><a id="X7C72994A825228E7" name="X7C72994A825228E7"></a></p>
<h5>7.2-8 LowerBoundCoveringRadiusVanWee2</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusVanWee2</code>( <var class="Arg">n, M, false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called using the syntax <code class="code">LowerBoundCoveringRadiusVanWee2( n, r [,true] )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusVanWee2</code> is <var class="Arg">false</var>, then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p>This bound only works for binary codes. It is based on the following inequality:</p>
<p class="pcenter">
M \cdot \frac{\left( \left( V_2(n,2) - \frac{1}{2}(r+2)(r-1) \right)
V_2(n,r) + \varepsilon
V_2(n,r-2) \right)}
{(V_2(n,2) - \frac{1}{2}(r+2)(r-1) + \varepsilon)}
\geq 2^n,
</p>
<p>where</p>
<p class="pcenter">
\varepsilon = {r+2 \choose 2} \left\lceil
{n-r+1 \choose 2} / {r+2 \choose 2} \right\rceil
- {n-r+1 \choose 2}.
</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
3
gap> LowerBoundCoveringRadiusVanWee2(10,32,false);
2
gap> LowerBoundCoveringRadiusVanWee2(10,3,true);
7
</pre></td></tr></table>
<p><a id="X7F95362485759ACB" name="X7F95362485759ACB"></a></p>
<h5>7.2-9 LowerBoundCoveringRadiusCountingExcess</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusCountingExcess</code>( <var class="Arg">n, M, false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called with <code class="code">LowerBoundCoveringRadiusCountingExcess( n, r [,true] )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusCountingExcess</code> is <var class="Arg">false</var>, then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p>This bound only works for binary codes. It is based on the following inequality:</p>
<p class="pcenter">
M \cdot \left( \rho V_2(n,r) + \varepsilon V_2(n,r-1) \right) \geq
(\rho + \varepsilon) 2^n,
</p>
<p>where</p>
<p class="pcenter">
\varepsilon = (r+1) \left\lceil\frac{n+1}{r+1}\right\rceil - (n+1)
</p>
<p>and</p>
<p class="pcenter">
\rho = \left\{
\begin{array}{l}
n-3+\frac{2}{n}, \ \ \ \ \ \ {\rm if}\ r = 2\\
n-r-1 , \ \ \ \ \ \ {\rm if}\ r \geq 3 .
\end{array}
\right.
</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
3
gap> LowerBoundCoveringRadiusCountingExcess(10,32,false);
0
gap> LowerBoundCoveringRadiusCountingExcess(10,3,true);
7
</pre></td></tr></table>
<p><a id="X829C14A383B5BF59" name="X829C14A383B5BF59"></a></p>
<h5>7.2-10 LowerBoundCoveringRadiusEmbedded1</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusEmbedded1</code>( <var class="Arg">n, M, false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called with <code class="code">LowerBoundCoveringRadiusEmbedded1( n, r [,true] )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusEmbedded1</code> is 'false', then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p>This bound only works for binary codes. It is based on the following inequality:</p>
<p class="pcenter">
M \cdot \left( V_2(n,r) - {2r \choose r} \right) \geq
2^n - A( n, 2r+1 ) {2r \choose r},
</p>
<p>where A(n,d) denotes the maximal cardinality of a (binary) code of length n and minimum distance d. The function <code class="code">UpperBound</code> is used to compute this value.</p>
<p>Sometimes <code class="code">LowerBoundCoveringRadiusEmbedded1</code> is better than <code class="code">LowerBoundCoveringRadiusEmbedded2</code>, sometimes it is the other way around.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(10,5,GF(2));
a [10,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
3
gap> LowerBoundCoveringRadiusEmbedded1(10,32,false);
2
gap> LowerBoundCoveringRadiusEmbedded1(10,3,true);
7
</pre></td></tr></table>
<p><a id="X7B0C81B88604C448" name="X7B0C81B88604C448"></a></p>
<h5>7.2-11 LowerBoundCoveringRadiusEmbedded2</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusEmbedded2</code>( <var class="Arg">n, M, false</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command can also be called with <code class="code">LowerBoundCoveringRadiusEmbedded2( n, r [,true] )</code>. If the last argument of <code class="code">LowerBoundCoveringRadiusEmbedded2</code> is 'false', then it returns a lower bound for the covering radius of a code of size <var class="Arg">M</var> and length <var class="Arg">n</var>. Otherwise, it returns a lower bound for the size of a code of length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p>This bound only works for binary codes. It is based on the following inequality:</p>
<p class="pcenter">
M \cdot \left( V_2(n,r) - \frac{3}{2} {2r \choose r} \right) \geq
2^n - 2A( n, 2r+1 ) {2r \choose r},
</p>
<p>where A(n,d) denotes the maximal cardinality of a (binary) code of length n and minimum distance d. The function <code class="code">UpperBound</code> is used to compute this value.</p>
<p>Sometimes <code class="code">LowerBoundCoveringRadiusEmbedded1</code> is better than <code class="code">LowerBoundCoveringRadiusEmbedded2</code>, sometimes it is the other way around.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> Size(C);
32
gap> CoveringRadius(C);
6
gap> LowerBoundCoveringRadiusEmbedded2(10,32,false);
2
gap> LowerBoundCoveringRadiusEmbedded2(10,3,true);
7
</pre></td></tr></table>
<p><a id="X7D27F6E27B9A0D35" name="X7D27F6E27B9A0D35"></a></p>
<h5>7.2-12 LowerBoundCoveringRadiusInduction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LowerBoundCoveringRadiusInduction</code>( <var class="Arg">n, r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">LowerBoundCoveringRadiusInduction</code> returns a lower bound for the size of a code with length <var class="Arg">n</var> and covering radius <var class="Arg">r</var>.</p>
<p>If n = 2r+2 and r >= 1, the returned value is 4.</p>
<p>If n = 2r+3 and r >= 1, the returned value is 7.</p>
<p>If n = 2r+4 and r >= 4, the returned value is 8.</p>
<p>Otherwise, 0 is returned.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> CoveringRadius(C);
5
gap> LowerBoundCoveringRadiusInduction(15,6);
7
</pre></td></tr></table>
<p><a id="X80F8DFAD7D67CBEC" name="X80F8DFAD7D67CBEC"></a></p>
<h5>7.2-13 UpperBoundCoveringRadiusRedundancy</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundCoveringRadiusRedundancy</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">UpperBoundCoveringRadiusRedundancy</code> returns the redundancy of <var class="Arg">C</var> as an upper bound for the covering radius of <var class="Arg">C</var>. <var class="Arg">C</var> must be a linear code.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> CoveringRadius(C);
5
gap> UpperBoundCoveringRadiusRedundancy(C);
10
</pre></td></tr></table>
<p><a id="X832847A17FD0D142" name="X832847A17FD0D142"></a></p>
<h5>7.2-14 UpperBoundCoveringRadiusDelsarte</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundCoveringRadiusDelsarte</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">UpperBoundCoveringRadiusDelsarte</code> returns an upper bound for the covering radius of <var class="Arg">C</var>. This upper bound is equal to the external distance of <var class="Arg">C</var>, this is the minimum distance of the dual code, if <var class="Arg">C</var> is a linear code.</p>
<p>This is described in Theorem 11.3.3 of <a href="chapBib.html#biBHP03">[HP03]</a>.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> CoveringRadius(C);
5
gap> UpperBoundCoveringRadiusDelsarte(C);
13
</pre></td></tr></table>
<p><a id="X86F10D9E79AB8796" name="X86F10D9E79AB8796"></a></p>
<h5>7.2-15 UpperBoundCoveringRadiusStrength</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundCoveringRadiusStrength</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">UpperBoundCoveringRadiusStrength</code> returns an upper bound for the covering radius of <var class="Arg">C</var>.</p>
<p>First the code is punctured at the zero coordinates (i.e. the coordinates where all codewords have a zero). If the remaining code has <em>strength</em> 1 (i.e. each coordinate contains each element of the field an equal number of times), then it returns fracq-1qm + (n-m) (where q is the size of the field and m is the length of punctured code), otherwise it returns n. This bound works for all codes.</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> CoveringRadius(C);
5
gap> UpperBoundCoveringRadiusStrength(C);
7
</pre></td></tr></table>
<p><a id="X8585C6A982489FC3" name="X8585C6A982489FC3"></a></p>
<h5>7.2-16 UpperBoundCoveringRadiusGriesmerLike</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundCoveringRadiusGriesmerLike</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function returns an upper bound for the covering radius of <var class="Arg">C</var>, which must be linear, in a Griesmer-like fashion. It returns</p>
<p class="pcenter">
n - \sum_{i=1}^k \left\lceil \frac{d}{q^i} \right\rceil
</p>
<table class="example">
<tr><td><pre>
gap> C:=RandomLinearCode(15,5,GF(2));
a [15,5,?] randomly generated code over GF(2)
gap> CoveringRadius(C);
5
gap> UpperBoundCoveringRadiusGriesmerLike(C);
9
</pre></td></tr></table>
<p><a id="X82A38F5F858CF3FC" name="X82A38F5F858CF3FC"></a></p>
<h5>7.2-17 UpperBoundCoveringRadiusCyclicCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UpperBoundCoveringRadiusCyclicCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function returns an upper bound for the covering radius of <var class="Arg">C</var>, which must be a cyclic code. It returns</p>
<p class="pcenter">
n - k + 1 - \left\lceil \frac{w(g(x))}{2} \right\rceil,
</p>
<p>where g(x) is the generator polynomial of <var class="Arg">C</var>.</p>
<table class="example">
<tr><td><pre>
gap> C:=CyclicCodes(15,GF(2))[3];
a cyclic [15,12,1..2]1..3 enumerated code over GF(2)
gap> CoveringRadius(C);
3
gap> UpperBoundCoveringRadiusCyclicCode(C);
3
</pre></td></tr></table>
<p><a id="X806EBEC77C16E657" name="X806EBEC77C16E657"></a></p>
<h4>7.3 <span class="Heading">
Special matrices in <strong class="pkg">GUAVA</strong>
</span></h4>
<p>This section explains functions that work with special matrices <strong class="pkg">GUAVA</strong> needs for several codes.</p>
<p>Firstly, we describe some matrix generating functions (see <code class="func">KrawtchoukMat</code> (<a href="chap7.html#X82899B64802A4BCE"><b>7.3-1</b></a>), <code class="func">GrayMat</code> (<a href="chap7.html#X87AFE2C078031CE4"><b>7.3-2</b></a>), <code class="func">SylvesterMat</code> (<a href="chap7.html#X7E1E7C5287919CDB"><b>7.3-3</b></a>), <code class="func">HadamardMat</code> (<a href="chap7.html#X8014A1F181ECD8AA"><b>7.3-4</b></a>) and <code class="func">MOLS</code> (<a href="chap7.html#X804AAFF2867080F7"><b>7.3-11</b></a>)).</p>
<p>Next we describe two functions regarding a standard form of matrices (see <code class="func">PutStandardForm</code> (<a href="chap7.html#X7B47D82485B66F1D"><b>7.3-6</b></a>) and <code class="func">IsInStandardForm</code> (<a href="chap7.html#X7D4EDA0A854EBFEF"><b>7.3-7</b></a>)).</p>
<p>Then we describe functions that return a matrix after a manipulation (see <code class="func">PermutedCols</code> (<a href="chap7.html#X7A97AD477E7638DE"><b>7.3-8</b></a>), <code class="func">VerticalConversionFieldMat</code> (<a href="chap7.html#X7B68119F85E9EC6D"><b>7.3-9</b></a>) and <code class="func">HorizontalConversionFieldMat</code> (<a href="chap7.html#X8033E9A67BA155C8"><b>7.3-10</b></a>)).</p>
<p>Finally, we describe functions that do some tests on matrices (see <code class="func">IsLatinSquare</code> (<a href="chap7.html#X7F34306B81DC2776"><b>7.3-12</b></a>) and <code class="func">AreMOLS</code> (<a href="chap7.html#X81B9B40B7B2D97D5"><b>7.3-13</b></a>)).</p>
<p><a id="X82899B64802A4BCE" name="X82899B64802A4BCE"></a></p>
<h5>7.3-1 KrawtchoukMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> KrawtchoukMat</code>( <var class="Arg">n, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">KrawtchoukMat</code> returns the n+1 by n+1 matrix K=(k_ij) defined by k_ij=K_i(j) for i,j=0,...,n. K_i(j) is the Krawtchouk number (see <code class="func">Krawtchouk</code> (<a href="chap7.html#X7ACDC5377CD17451"><b>7.5-6</b></a>)). <var class="Arg">n</var> must be a positive integer and <var class="Arg">q</var> a prime power. The Krawtchouk matrix is used in the <em>MacWilliams identities</em>, defining the relation between the weight distribution of a code of length <var class="Arg">n</var> over a field of size <var class="Arg">q</var>, and its dual code. Each call to <code class="code">KrawtchoukMat</code> returns a new matrix, so it is safe to modify the result.</p>
<table class="example">
<tr><td><pre>
gap> PrintArray( KrawtchoukMat( 3, 2 ) );
[ [ 1, 1, 1, 1 ],
[ 3, 1, -1, -3 ],
[ 3, -1, -1, 3 ],
[ 1, -1, 1, -1 ] ]
gap> C := HammingCode( 3 );; a := WeightDistribution( C );
[ 1, 0, 0, 7, 7, 0, 0, 1 ]
gap> n := WordLength( C );; q := Size( LeftActingDomain( C ) );;
gap> k := Dimension( C );;
gap> q^( -k ) * KrawtchoukMat( n, q ) * a;
[ 1, 0, 0, 0, 7, 0, 0, 0 ]
gap> WeightDistribution( DualCode( C ) );
[ 1, 0, 0, 0, 7, 0, 0, 0 ]
</pre></td></tr></table>
<p><a id="X87AFE2C078031CE4" name="X87AFE2C078031CE4"></a></p>
<h5>7.3-2 GrayMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GrayMat</code>( <var class="Arg">n, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GrayMat</code> returns a list of all different vectors (see GAP's <code class="code">Vectors</code> command) of length <var class="Arg">n</var> over the field <var class="Arg">F</var>, using Gray ordering. <var class="Arg">n</var> must be a positive integer. This order has the property that subsequent vectors differ in exactly one coordinate. The first vector is always the null vector. Each call to <code class="code">GrayMat</code> returns a new matrix, so it is safe to modify the result.</p>
<table class="example">
<tr><td><pre>
gap> GrayMat(3);
[ [ 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0 ],
[ 0*Z(2), Z(2)^0, Z(2)^0 ], [ 0*Z(2), Z(2)^0, 0*Z(2) ],
[ Z(2)^0, Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0, Z(2)^0 ],
[ Z(2)^0, 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2), 0*Z(2) ] ]
gap> G := GrayMat( 4, GF(4) );; Length(G);
256 # the length of a GrayMat is always q^n
gap> G[101] - G[100];
[ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ]
</pre></td></tr></table>
<p><a id="X7E1E7C5287919CDB" name="X7E1E7C5287919CDB"></a></p>
<h5>7.3-3 SylvesterMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SylvesterMat</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">SylvesterMat</code> returns the nx n Sylvester matrix of order <var class="Arg">n</var>. This is a special case of the Hadamard matrices (see <code class="func">HadamardMat</code> (<a href="chap7.html#X8014A1F181ECD8AA"><b>7.3-4</b></a>)). For this construction, <var class="Arg">n</var> must be a power of 2. Each call to <code class="code">SylvesterMat</code> returns a new matrix, so it is safe to modify the result.</p>
<table class="example">
<tr><td><pre>
gap> PrintArray(SylvesterMat(2));
[ [ 1, 1 ],
[ 1, -1 ] ]
gap> PrintArray( SylvesterMat(4) );
[ [ 1, 1, 1, 1 ],
[ 1, -1, 1, -1 ],
[ 1, 1, -1, -1 ],
[ 1, -1, -1, 1 ] ]
</pre></td></tr></table>
<p><a id="X8014A1F181ECD8AA" name="X8014A1F181ECD8AA"></a></p>
<h5>7.3-4 HadamardMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> HadamardMat</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">HadamardMat</code> returns a Hadamard matrix of order <var class="Arg">n</var>. This is an nx n matrix with the property that the matrix multiplied by its transpose returns <var class="Arg">n</var> times the identity matrix. This is only possible for n=1, n=2 or in cases where <var class="Arg">n</var> is a multiple of 4. If the matrix does not exist or is not known (as of 1998), <code class="code">HadamardMat</code> returns an error. A large number of construction methods is known to create these matrices for different orders. <code class="code">HadamardMat</code> makes use of two construction methods (the Paley Type I and II constructions, and the Sylvester construction -- see <code class="func">SylvesterMat</code> (<a href="chap7.html#X7E1E7C5287919CDB"><b>7.3-3</b></a>)). These methods cover most of the possible Hadamard matrices, although some special algorithms have not been implemented yet. The following orders less than 100 do not yet have an implementation for a Hadamard matrix in <strong class="pkg">GUAVA</strong>: 52, 92.</p>
<table class="example">
<tr><td><pre>
gap> C := HadamardMat(8);; PrintArray(C);
[ [ 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 1, -1, 1, -1, 1, -1, 1, -1 ],
[ 1, 1, -1, -1, 1, 1, -1, -1 ],
[ 1, -1, -1, 1, 1, -1, -1, 1 ],
[ 1, 1, 1, 1, -1, -1, -1, -1 ],
[ 1, -1, 1, -1, -1, 1, -1, 1 ],
[ 1, 1, -1, -1, -1, -1, 1, 1 ],
[ 1, -1, -1, 1, -1, 1, 1, -1 ] ]
gap> C * TransposedMat(C) = 8 * IdentityMat( 8, 8 );
true
</pre></td></tr></table>
<p><a id="X797F43607AD8660D" name="X797F43607AD8660D"></a></p>
<h5>7.3-5 VandermondeMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VandermondeMat</code>( <var class="Arg">X, a</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">VandermondeMat</code> returns the (a+1)x n matrix of powers x_i^j where <var class="Arg">X</var> is a list of elements of a field, X= x_1,...,x_n, and <var class="Arg">a</var> is a non-negative integer.</p>
<table class="example">
<tr><td><pre>
gap> M:=VandermondeMat([Z(5),Z(5)^2,Z(5)^0,Z(5)^3],2);
[ [ Z(5)^0, Z(5), Z(5)^2 ], [ Z(5)^0, Z(5)^2, Z(5)^0 ],
[ Z(5)^0, Z(5)^0, Z(5)^0 ], [ Z(5)^0, Z(5)^3, Z(5)^2 ] ]
gap> Display(M);
1 2 4
1 4 1
1 1 1
1 3 4
</pre></td></tr></table>
<p><a id="X7B47D82485B66F1D" name="X7B47D82485B66F1D"></a></p>
<h5>7.3-6 PutStandardForm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PutStandardForm</code>( <var class="Arg">M[, idleft]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>We say that a kx n matrix is in <em>standard form</em> if it is equal to the block matrix (I | A), for some kx (n-k) matrix A and where I is the kx k identity matrix. It follows from a basis result in linear algebra that, after a possible permutation of the columns, using elementary row operations, every matrix can be reduced to standard form. <code class="code">PutStandardForm</code> puts a matrix <var class="Arg">M</var> in standard form, and returns the permutation needed to do so. <var class="Arg">idleft</var> is a boolean that sets the position of the identity matrix in <var class="Arg">M</var>. (The default for <var class="Arg">idleft</var> is `true'.) If <var class="Arg">idleft</var> is set to `true', the identity matrix is put on the left side of <var class="Arg">M</var>. Otherwise, it is put at the right side. (This option is useful when putting a check matrix of a code into standard form.) The function <code class="code">BaseMat</code> also returns a similar standard form, but does not apply column permutations. The rows of the matrix still span the same vector space after <code class="code">BaseMat</code>, but after calling <code class="code">PutStandardForm</code>, this is not necessarily true.</p>
<table class="example">
<tr><td><pre>
gap> M := Z(2)*[[1,0,0,1],[0,0,1,1]];; PrintArray(M);
[ [ Z(2), 0*Z(2), 0*Z(2), Z(2) ],
[ 0*Z(2), 0*Z(2), Z(2), Z(2) ] ]
gap> PutStandardForm(M); # identity at the left side
(2,3)
gap> PrintArray(M);
[ [ Z(2), 0*Z(2), 0*Z(2), Z(2) ],
[ 0*Z(2), Z(2), 0*Z(2), Z(2) ] ]
gap> PutStandardForm(M, false); # identity at the right side
(1,4,3)
gap> PrintArray(M);
[ [ 0*Z(2), Z(2), Z(2), 0*Z(2) ],
[ 0*Z(2), Z(2), 0*Z(2), Z(2) ] ]
gap> C := BestKnownLinearCode( 23, 12, GF(2) );
a linear [23,12,7]3 punctured code
gap> G:=MutableCopyMat(GeneratorMat(C));;
gap> PutStandardForm(G);
()
gap> Display(G);
1 . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1
. 1 . . . . . . . . . . 1 1 1 1 1 . . 1 . . .
. . 1 . . . . . . . . . 1 1 . 1 . . 1 . 1 . 1
. . . 1 . . . . . . . . 1 1 . . . 1 1 1 . 1 .
. . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 . 1
. . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 1
. . . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1
. . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 . .
. . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 .
. . . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 .
. . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1 1
. . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1
</pre></td></tr></table>
<p><a id="X7D4EDA0A854EBFEF" name="X7D4EDA0A854EBFEF"></a></p>
<h5>7.3-7 IsInStandardForm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsInStandardForm</code>( <var class="Arg">M[, idleft]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsInStandardForm</code> determines if <var class="Arg">M</var> is in standard form. <var class="Arg">idleft</var> is a boolean that indicates the position of the identity matrix in <var class="Arg">M</var>, as in <code class="code">PutStandardForm</code> (see <code class="func">PutStandardForm</code> (<a href="chap7.html#X7B47D82485B66F1D"><b>7.3-6</b></a>)). <code class="code">IsInStandardForm</code> checks if the identity matrix is at the left side of <var class="Arg">M</var>, otherwise if it is at the right side. The elements of <var class="Arg">M</var> may be elements of any field.</p>
<table class="example">
<tr><td><pre>
gap> IsInStandardForm(IdentityMat(7, GF(2)));
true
gap> IsInStandardForm([[1, 1, 0], [1, 0, 1]], false);
true
gap> IsInStandardForm([[1, 3, 2, 7]]);
true
gap> IsInStandardForm(HadamardMat(4));
false
</pre></td></tr></table>
<p><a id="X7A97AD477E7638DE" name="X7A97AD477E7638DE"></a></p>
<h5>7.3-8 PermutedCols</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PermutedCols</code>( <var class="Arg">M, P</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PermutedCols</code> returns a matrix <var class="Arg">M</var> with a permutation <var class="Arg">P</var> applied to its columns.</p>
<table class="example">
<tr><td><pre>
gap> M := [[1,2,3,4],[1,2,3,4]];; PrintArray(M);
[ [ 1, 2, 3, 4 ],
[ 1, 2, 3, 4 ] ]
gap> PrintArray(PermutedCols(M, (1,2,3)));
[ [ 3, 1, 2, 4 ],
[ 3, 1, 2, 4 ] ]
</pre></td></tr></table>
<p><a id="X7B68119F85E9EC6D" name="X7B68119F85E9EC6D"></a></p>
<h5>7.3-9 VerticalConversionFieldMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VerticalConversionFieldMat</code>( <var class="Arg">M, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">VerticalConversionFieldMat</code> returns the matrix <var class="Arg">M</var> with its elements converted from a field F=GF(q^m), q prime, to a field GF(q). Each element is replaced by its representation over the latter field, placed vertically in the matrix, using the GF(p)-vector space isomorphism</p>
<p class="pcenter">
[...] : GF(q)\rightarrow GF(p)^m,
</p>
<p>with q=p^m.</p>
<p>If <var class="Arg">M</var> is a k by n matrix, the result is a k* m x n matrix, since each element of GF(q^m) can be represented in GF(q) using m elements.</p>
<table class="example">
<tr><td><pre>
gap> M := Z(9)*[[1,2],[2,1]];; PrintArray(M);
[ [ Z(3^2), Z(3^2)^5 ],
[ Z(3^2)^5, Z(3^2) ] ]
gap> DefaultField( Flat(M) );
GF(3^2)
gap> VCFM := VerticalConversionFieldMat( M, GF(9) );; PrintArray(VCFM);
[ [ 0*Z(3), 0*Z(3) ],
[ Z(3)^0, Z(3) ],
[ 0*Z(3), 0*Z(3) ],
[ Z(3), Z(3)^0 ] ]
gap> DefaultField( Flat(VCFM) );
GF(3)
</pre></td></tr></table>
<p>A similar function is <code class="code">HorizontalConversionFieldMat</code> (see <code class="func">HorizontalConversionFieldMat</code> (<a href="chap7.html#X8033E9A67BA155C8"><b>7.3-10</b></a>)).</p>
<p><a id="X8033E9A67BA155C8" name="X8033E9A67BA155C8"></a></p>
<h5>7.3-10 HorizontalConversionFieldMat</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> HorizontalConversionFieldMat</code>( <var class="Arg">M, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">HorizontalConversionFieldMat</code> returns the matrix <var class="Arg">M</var> with its elements converted from a field F=GF(q^m), q prime, to a field GF(q). Each element is replaced by its representation over the latter field, placed horizontally in the matrix.</p>
<p>If <var class="Arg">M</var> is a k x n matrix, the result is a kx mx n* m matrix. The new word length of the resulting code is equal to n* m, because each element of GF(q^m) can be represented in GF(q) using m elements. The new dimension is equal to kx m because the new matrix should be a basis for the same number of vectors as the old one.</p>
<p><code class="code">ConversionFieldCode</code> uses horizontal conversion to convert a code (see <code class="func">ConversionFieldCode</code> (<a href="chap6.html#X81FE1F387DFCCB22"><b>6.1-15</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> M := Z(9)*[[1,2],[2,1]];; PrintArray(M);
[ [ Z(3^2), Z(3^2)^5 ],
[ Z(3^2)^5, Z(3^2) ] ]
gap> DefaultField( Flat(M) );
GF(3^2)
gap> HCFM := HorizontalConversionFieldMat(M, GF(9));; PrintArray(HCFM);
[ [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3) ],
[ Z(3)^0, Z(3)^0, Z(3), Z(3) ],
[ 0*Z(3), Z(3), 0*Z(3), Z(3)^0 ],
[ Z(3), Z(3), Z(3)^0, Z(3)^0 ] ]
gap> DefaultField( Flat(HCFM) );
GF(3)
</pre></td></tr></table>
<p>A similar function is <code class="code">VerticalConversionFieldMat</code> (see <code class="func">VerticalConversionFieldMat</code> (<a href="chap7.html#X7B68119F85E9EC6D"><b>7.3-9</b></a>)).</p>
<p><a id="X804AAFF2867080F7" name="X804AAFF2867080F7"></a></p>
<h5>7.3-11 MOLS</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MOLS</code>( <var class="Arg">q[, n]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">MOLS</code> returns a list of <var class="Arg">n</var> <em>Mutually Orthogonal Latin Squares</em> (MOLS). A <em>Latin square</em> of order <var class="Arg">q</var> is a qx q matrix whose entries are from a set F_q of <var class="Arg">q</var> distinct symbols (<strong class="pkg">GUAVA</strong> uses the integers from 0 to <var class="Arg">q</var>) such that each row and each column of the matrix contains each symbol exactly once.</p>
<p>A set of Latin squares is a set of MOLS if and only if for each pair of Latin squares in this set, every ordered pair of elements that are in the same position in these matrices occurs exactly once.</p>
<p><var class="Arg">n</var> must be less than <var class="Arg">q</var>. If <var class="Arg">n</var> is omitted, two MOLS are returned. If <var class="Arg">q</var> is not a prime power, at most 2 MOLS can be created. For all values of <var class="Arg">q</var> with q > 2 and q <> 6, a list of MOLS can be constructed. However, <strong class="pkg">GUAVA</strong> does not yet construct MOLS for q= 2 mod 4. If it is not possible to construct <var class="Arg">n</var> MOLS, the function returns `false'.</p>
<p>MOLS are used to create <var class="Arg">q</var>-ary codes (see <code class="func">MOLSCode</code> (<a href="chap5.html#X81B7EE4279398F67"><b>5.1-4</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> M := MOLS( 4, 3 );;PrintArray( M[1] );
[ [ 0, 1, 2, 3 ],
[ 1, 0, 3, 2 ],
[ 2, 3, 0, 1 ],
[ 3, 2, 1, 0 ] ]
gap> PrintArray( M[2] );
[ [ 0, 2, 3, 1 ],
[ 1, 3, 2, 0 ],
[ 2, 0, 1, 3 ],
[ 3, 1, 0, 2 ] ]
gap> PrintArray( M[3] );
[ [ 0, 3, 1, 2 ],
[ 1, 2, 0, 3 ],
[ 2, 1, 3, 0 ],
[ 3, 0, 2, 1 ] ]
gap> MOLS( 12, 3 );
false
</pre></td></tr></table>
<p><a id="X7F34306B81DC2776" name="X7F34306B81DC2776"></a></p>
<h5>7.3-12 IsLatinSquare</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsLatinSquare</code>( <var class="Arg">M</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsLatinSquare</code> determines if a matrix <var class="Arg">M</var> is a Latin square. For a Latin square of size nx n, each row and each column contains all the integers 1,dots,n exactly once.</p>
<table class="example">
<tr><td><pre>
gap> IsLatinSquare([[1,2],[2,1]]);
true
gap> IsLatinSquare([[1,2,3],[2,3,1],[1,3,2]]);
false
</pre></td></tr></table>
<p><a id="X81B9B40B7B2D97D5" name="X81B9B40B7B2D97D5"></a></p>
<h5>7.3-13 AreMOLS</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AreMOLS</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">AreMOLS</code> determines if <var class="Arg">L</var> is a list of mutually orthogonal Latin squares (MOLS). For each pair of Latin squares in this list, the function checks if each ordered pair of elements that are in the same position in these matrices occurs exactly once. The function <code class="code">MOLS</code> creates MOLS (see <code class="func">MOLS</code> (<a href="chap7.html#X804AAFF2867080F7"><b>7.3-11</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> M := MOLS(4,2);
[ [ [ 0, 1, 2, 3 ], [ 1, 0, 3, 2 ], [ 2, 3, 0, 1 ], [ 3, 2, 1, 0 ] ],
[ [ 0, 2, 3, 1 ], [ 1, 3, 2, 0 ], [ 2, 0, 1, 3 ], [ 3, 1, 0, 2 ] ] ]
gap> AreMOLS(M);
true
</pre></td></tr></table>
<p><a id="X7AB5E5CE7FDF7132" name="X7AB5E5CE7FDF7132"></a></p>
<h4>7.4 <span class="Heading">
Some functions related to the norm of a code
</span></h4>
<p>In this section, some functions that can be used to compute the norm of a code and to decide upon its normality are discussed. Typically, these are applied to binary linear codes. The definitions of this section were introduced in Graham and Sloane <a href="chapBib.html#biBGS85">[GS85]</a>.</p>
<p><a id="X8032E53078264ABB" name="X8032E53078264ABB"></a></p>
<h5>7.4-1 CoordinateNorm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CoordinateNorm</code>( <var class="Arg">C, coord</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CoordinateNorm</code> returns the norm of <var class="Arg">C</var> with respect to coordinate <var class="Arg">coord</var>. If C_a = c in C | c_coord = a, then the norm of <var class="Arg">C</var> with respect to <var class="Arg">coord</var> is defined as</p>
<p class="pcenter">
\max_{v \in GF(q)^n} \sum_{a=1}^q d(x,C_a),
</p>
<p>with the convention that d(x,C_a) = n if C_a is empty.</p>
<table class="example">
<tr><td><pre>
gap> CoordinateNorm( HammingCode( 3, GF(2) ), 3 );
3
</pre></td></tr></table>
<p><a id="X7ED2EF368203AF47" name="X7ED2EF368203AF47"></a></p>
<h5>7.4-2 CodeNorm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodeNorm</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodeNorm</code> returns the norm of <var class="Arg">C</var>. The <em>norm</em> of a code is defined as the minimum of the norms for the respective coordinates of the code. In effect, for each coordinate <code class="code">CoordinateNorm</code> is called, and the minimum of the calculated numbers is returned.</p>
<table class="example">
<tr><td><pre>
gap> CodeNorm( HammingCode( 3, GF(2) ) );
3
</pre></td></tr></table>
<p><a id="X7D24F8BF7F9A7BF1" name="X7D24F8BF7F9A7BF1"></a></p>
<h5>7.4-3 IsCoordinateAcceptable</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsCoordinateAcceptable</code>( <var class="Arg">C, coord</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsCoordinateAcceptable</code> returns `true' if coordinate <var class="Arg">coord</var> of <var class="Arg">C</var> is acceptable. A coordinate is called <em>acceptable</em> if the norm of the code with respect to that coordinate is not more than two times the covering radius of the code plus one.</p>
<table class="example">
<tr><td><pre>
gap> IsCoordinateAcceptable( HammingCode( 3, GF(2) ), 3 );
true
</pre></td></tr></table>
<p><a id="X87039FD179AD3009" name="X87039FD179AD3009"></a></p>
<h5>7.4-4 GeneralizedCodeNorm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneralizedCodeNorm</code>( <var class="Arg">C, subcode1, subscode2, ..., subcodek</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">GeneralizedCodeNorm</code> returns the <var class="Arg">k</var>-norm of <var class="Arg">C</var> with respect to <var class="Arg">k</var> subcodes.</p>
<table class="example">
<tr><td><pre>
gap> c := RepetitionCode( 7, GF(2) );;
gap> ham := HammingCode( 3, GF(2) );;
gap> d := EvenWeightSubcode( ham );;
gap> e := ConstantWeightSubcode( ham, 3 );;
gap> GeneralizedCodeNorm( ham, c, d, e );
4
</pre></td></tr></table>
<p><a id="X80283A2F7C8101BD" name="X80283A2F7C8101BD"></a></p>
<h5>7.4-5 IsNormalCode</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsNormalCode</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">IsNormalCode</code> returns `true' if <var class="Arg">C</var> is normal. A code is called <em>normal</em> if the norm of the code is not more than two times the covering radius of the code plus one. Almost all codes are normal, however some (non-linear) abnormal codes have been found.</p>
<p>Often, it is difficult to find out whether a code is normal, because it involves computing the covering radius. However, <code class="code">IsNormalCode</code> uses much information from the literature (in particular, <a href="chapBib.html#biBGS85">[GS85]</a>) about normality for certain code parameters.</p>
<table class="example">
<tr><td><pre>
gap> IsNormalCode( HammingCode( 3, GF(2) ) );
true
</pre></td></tr></table>
<p><a id="X8308D685809A4E2F" name="X8308D685809A4E2F"></a></p>
<h4>7.5 <span class="Heading">
Miscellaneous functions
</span></h4>
<p>In this section we describe several vector space functions <strong class="pkg">GUAVA</strong> uses for constructing codes or performing calculations with codes.</p>
<p>In this section, some new miscellaneous functions are described, including weight enumerators, the MacWilliams-transform and affinity and almost affinity of codes.</p>
<p><a id="X871286437DE7A6A4" name="X871286437DE7A6A4"></a></p>
<h5>7.5-1 CodeWeightEnumerator</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodeWeightEnumerator</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodeWeightEnumerator</code> returns a polynomial of the following form:</p>
<p class="pcenter">
f(x) = \sum_{i=0}^{n} A_i x^i,
</p>
<p>where A_i is the number of codewords in <var class="Arg">C</var> with weight i.</p>
<table class="example">
<tr><td><pre>
gap> CodeWeightEnumerator( ElementsCode( [ [ 0,0,0 ], [ 0,0,1 ],
> [ 0,1,1 ], [ 1,1,1 ] ], GF(2) ) );
x^3 + x^2 + x + 1
gap> CodeWeightEnumerator( HammingCode( 3, GF(2) ) );
x^7 + 7*x^4 + 7*x^3 + 1
</pre></td></tr></table>
<p><a id="X84DA928083B103A0" name="X84DA928083B103A0"></a></p>
<h5>7.5-2 CodeDistanceEnumerator</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodeDistanceEnumerator</code>( <var class="Arg">C, w</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodeDistanceEnumerator</code> returns a polynomial of the following form:</p>
<p class="pcenter">
f(x) = \sum_{i=0}^{n} B_i x^i,
</p>
<p>where B_i is the number of codewords with distance i to <var class="Arg">w</var>.</p>
<p>If <var class="Arg">w</var> is a codeword, then <code class="code">CodeDistanceEnumerator</code> returns the same polynomial as <code class="code">CodeWeightEnumerator</code>.</p>
<table class="example">
<tr><td><pre>
gap> CodeDistanceEnumerator( HammingCode( 3, GF(2) ),[0,0,0,0,0,0,1] );
x^6 + 3*x^5 + 4*x^4 + 4*x^3 + 3*x^2 + x
gap> CodeDistanceEnumerator( HammingCode( 3, GF(2) ),[1,1,1,1,1,1,1] );
x^7 + 7*x^4 + 7*x^3 + 1 # `[1,1,1,1,1,1,1]' $\in$ `HammingCode( 3, GF(2 ) )'
</pre></td></tr></table>
<p><a id="X84B2BE66780EFBF9" name="X84B2BE66780EFBF9"></a></p>
<h5>7.5-3 CodeMacWilliamsTransform</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodeMacWilliamsTransform</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodeMacWilliamsTransform</code> returns a polynomial of the following form:</p>
<p class="pcenter">
f(x) = \sum_{i=0}^{n} C_i x^i,
</p>
<p>where C_i is the number of codewords with weight i in the <em>dual</em> code of <var class="Arg">C</var>.</p>
<table class="example">
<tr><td><pre>
gap> CodeMacWilliamsTransform( HammingCode( 3, GF(2) ) );
7*x^4 + 1
</pre></td></tr></table>
<p><a id="X7903286078F8051B" name="X7903286078F8051B"></a></p>
<h5>7.5-4 CodeDensity</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CodeDensity</code>( <var class="Arg">C</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CodeDensity</code> returns the <em>density</em> of <var class="Arg">C</var>. The density of a code is defined as</p>
<p class="pcenter">
\frac{M \cdot V_q(n,t)}{q^n},
</p>
<p>where M is the size of the code, V_q(n,t) is the size of a sphere of radius t in GF(q^n) (which may be computed using <code class="code">SphereContent</code>), t is the covering radius of the code and n is the length of the code.</p>
<table class="example">
<tr><td><pre>
gap> CodeDensity( HammingCode( 3, GF(2) ) );
1
gap> CodeDensity( ReedMullerCode( 1, 4 ) );
14893/2048
</pre></td></tr></table>
<p><a id="X85303BAE7BD46D81" name="X85303BAE7BD46D81"></a></p>
<h5>7.5-5 SphereContent</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SphereContent</code>( <var class="Arg">n, t, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">SphereContent</code> returns the content of a ball of radius <var class="Arg">t</var> around an arbitrary element of the vectorspace F^n. This is the cardinality of the set of all elements of F^n that are at distance (see <code class="func">DistanceCodeword</code> (<a href="chap3.html#X7CDA1B547D55E6FB"><b>3.6-2</b></a>) less than or equal to <var class="Arg">t</var> from an element of F^n.</p>
<p>In the context of codes, the function is used to determine if a code is perfect. A code is <em>perfect</em> if spheres of radius t around all codewords partition the whole ambient vector space, where <em>t</em> is the number of errors the code can correct.</p>
<table class="example">
<tr><td><pre>
gap> SphereContent( 15, 0, GF(2) );
1 # Only one word with distance 0, which is the word itself
gap> SphereContent( 11, 3, GF(4) );
4984
gap> C := HammingCode(5);
a linear [31,26,3]1 Hamming (5,2) code over GF(2)
#the minimum distance is 3, so the code can correct one error
gap> ( SphereContent( 31, 1, GF(2) ) * Size(C) ) = 2 ^ 31;
true
</pre></td></tr></table>
<p><a id="X7ACDC5377CD17451" name="X7ACDC5377CD17451"></a></p>
<h5>7.5-6 Krawtchouk</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Krawtchouk</code>( <var class="Arg">k, i, n, q</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">Krawtchouk</code> returns the Krawtchouk number K_k(i). <var class="Arg">q</var> must be a prime power, <var class="Arg">n</var> must be a positive integer, <var class="Arg">k</var> must be a non-negative integer less then or equal to <var class="Arg">n</var> and <var class="Arg">i</var> can be any integer. (See <code class="func">KrawtchoukMat</code> (<a href="chap7.html#X82899B64802A4BCE"><b>7.3-1</b></a>)). This number is the value at x=i of the polynomial</p>
<p class="pcenter">
K_k^{n,q}(x)
=\sum_{j=0}^n (-1)^j(q-1)^{k-j}b(x,j)b(n-x,k-j),
</p>
<p>where $b(v,u)=u!/(v!(v-u)!)$ is the binomial coefficient if $u,v$ are integers. For more properties of these polynomials, see <a href="chapBib.html#biBMS83">[MS83]</a>.</p>
<table class="example">
<tr><td><pre>
gap> Krawtchouk( 2, 0, 3, 2);
3
</pre></td></tr></table>
<p><a id="X827E39957A87EB51" name="X827E39957A87EB51"></a></p>
<h5>7.5-7 PrimitiveUnityRoot</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PrimitiveUnityRoot</code>( <var class="Arg">F, n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PrimitiveUnityRoot</code> returns a primitive <var class="Arg">n</var>-th root of unity in an extension field of <var class="Arg">F</var>. This is a finite field element a with the property a^n=1 in <var class="Arg">F</var>, and <var class="Arg">n</var> is the smallest integer such that this equality holds.</p>
<table class="example">
<tr><td><pre>
gap> PrimitiveUnityRoot( GF(2), 15 );
Z(2^4)
gap> last^15;
Z(2)^0
gap> PrimitiveUnityRoot( GF(8), 21 );
Z(2^6)^3
</pre></td></tr></table>
<p><a id="X78AEA40F7AD9D541" name="X78AEA40F7AD9D541"></a></p>
<h5>7.5-8 PrimitivePolynomialsNr</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PrimitivePolynomialsNr</code>( <var class="Arg">n, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PrimitivePolynomialsNr</code> returns the number of irreducible polynomials over F=GF(q) of degree <var class="Arg">n</var> with (maximum) period q^n-1. (According to a theorem of S. Golomb, this is phi(p^n-1)/n.)</p>
<p>See also the GAP function <code class="code">RandomPrimitivePolynomial</code>, <code class="func">RandomPrimitivePolynomial</code> (<a href="chap2.html#X7ECC593583E68A6C"><b>2.2-2</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> PrimitivePolynomialsNr(3,4);
12
</pre></td></tr></table>
<p><a id="X7A2B54EF868AA752" name="X7A2B54EF868AA752"></a></p>
<h5>7.5-9 IrreduciblePolynomialsNr</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IrreduciblePolynomialsNr</code>( <var class="Arg">n, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">PrimitivePolynomialsNr</code> returns the number of irreducible polynomials over F=GF(q) of degree <var class="Arg">n</var>.</p>
<table class="example">
<tr><td><pre>
gap> IrreduciblePolynomialsNr(3,4);
20
</pre></td></tr></table>
<p><a id="X7B50D3417F6FD7C6" name="X7B50D3417F6FD7C6"></a></p>
<h5>7.5-10 MatrixRepresentationOfElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MatrixRepresentationOfElement</code>( <var class="Arg">a, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Here <var class="Arg">F</var> is either a finite extension of the ``base field'' GF(p) or of the rationals Q}, and ain F. The command <code class="code">MatrixRepresentationOfElement</code> returns a matrix representation of <var class="Arg">a</var> over the base field.</p>
<p>If the element <var class="Arg">a</var> is defined over the base field then it returns the corresponding 1x 1 matrix.</p>
<table class="example">
<tr><td><pre>
gap> a:=Random(GF(4));
0*Z(2)
gap> M:=MatrixRepresentationOfElement(a,GF(4));; Display(M);
.
gap> a:=Random(GF(4));
Z(2^2)
gap> M:=MatrixRepresentationOfElement(a,GF(4));; Display(M);
. 1
1 1
gap>
</pre></td></tr></table>
<p><a id="X7805D2BB7CE4D455" name="X7805D2BB7CE4D455"></a></p>
<h5>7.5-11 ReciprocalPolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ReciprocalPolynomial</code>( <var class="Arg">P</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">ReciprocalPolynomial</code> returns the <em>reciprocal</em> of polynomial <var class="Arg">P</var>. This is a polynomial with coefficients of <var class="Arg">P</var> in the reverse order. So if P=a_0 + a_1 X + ... + a_n X^n, the reciprocal polynomial is P'=a_n + a_n-1 X + ... + a_0 X^n.</p>
<p>This command can also be called using the syntax <code class="code">ReciprocalPolynomial( P , n )</code>. In this form, the number of coefficients of <var class="Arg">P</var> is assumed to be less than or equal to n+1 (with zero coefficients added in the highest degrees, if necessary). Therefore, the reciprocal polynomial also has degree n+1.</p>
<table class="example">
<tr><td><pre>
gap> P := UnivariatePolynomial( GF(3), Z(3)^0 * [1,0,1,2] );
Z(3)^0+x_1^2-x_1^3
gap> RecP := ReciprocalPolynomial( P );
-Z(3)^0+x_1+x_1^3
gap> ReciprocalPolynomial( RecP ) = P;
true
gap> P := UnivariatePolynomial( GF(3), Z(3)^0 * [1,0,1,2] );
Z(3)^0+x_1^2-x_1^3
gap> ReciprocalPolynomial( P, 6 );
-x_1^3+x_1^4+x_1^6
</pre></td></tr></table>
<p><a id="X7AEA9F807E6FFEFF" name="X7AEA9F807E6FFEFF"></a></p>
<h5>7.5-12 CyclotomicCosets</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CyclotomicCosets</code>( <var class="Arg">q, n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="code">CyclotomicCosets</code> returns the cyclotomic cosets of q mod n. <var class="Arg">q</var> and <var class="Arg">n</var> must be relatively prime. Each of the elements of the returned list is a list of integers that belong to one cyclotomic coset. A q-cyclotomic coset of s mod n is a set of the form s,sq,sq^2,...,sq^r-1, where r is the smallest positive integer such that sq^r-s is 0 mod n. In other words, each coset contains all multiplications of the coset representative by q mod n. The coset representative is the smallest integer that isn't in the previous cosets.</p>
<table class="example">
<tr><td><pre>
gap> CyclotomicCosets( 2, 15 );
[ [ 0 ], [ 1, 2, 4, 8 ], [ 3, 6, 12, 9 ], [ 5, 10 ],
[ 7, 14, 13, 11 ] ]
gap> CyclotomicCosets( 7, 6 );
[ [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ]
</pre></td></tr></table>
<p><a id="X7A4EA98D794CF410" name="X7A4EA98D794CF410"></a></p>
<h5>7.5-13 WeightHistogram</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WeightHistogram</code>( <var class="Arg">C[, h]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">WeightHistogram</code> plots a histogram of weights in code <var class="Arg">C</var>. The maximum length of a column is <var class="Arg">h</var>. Default value for <var class="Arg">h</var> is 1/3 of the size of the screen. The number that appears at the top of the histogram is the maximum value of the list of weights.</p>
<table class="example">
<tr><td><pre>
gap> H := HammingCode(2, GF(5));
a linear [6,4,3]1 Hamming (2,5) code over GF(5)
gap> WeightDistribution(H);
[ 1, 0, 0, 80, 120, 264, 160 ]
gap> WeightHistogram(H);
264----------------
*
*
*
*
* *
* * *
* * * *
* * * *
+--------+--+--+--+--
0 1 2 3 4 5 6
</pre></td></tr></table>
<p><a id="X805DF25C84585FD6" name="X805DF25C84585FD6"></a></p>
<h5>7.5-14 MultiplicityInList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MultiplicityInList</code>( <var class="Arg">L, a</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This is a very simple list command which returns how many times a occurs in L. It returns 0 if a is not in L. (The GAP command <code class="code">Collected</code> does not quite handle this "extreme" case.)</p>
<table class="example">
<tr><td><pre>
gap> L:=[1,2,3,4,3,2,1,5,4,3,2,1];;
gap> MultiplicityInList(L,1);
3
gap> MultiplicityInList(L,6);
0
</pre></td></tr></table>
<p><a id="X8072B0DA78FBE562" name="X8072B0DA78FBE562"></a></p>
<h5>7.5-15 MostCommonInList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MostCommonInList</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Input: a list L</p>
<p>Output: an a in L which occurs at least as much as any other in L</p>
<table class="example">
<tr><td><pre>
gap> L:=[1,2,3,4,3,2,1,5,4,3,2,1];;
gap> MostCommonInList(L);
1
</pre></td></tr></table>
<p><a id="X7C5407EF87849857" name="X7C5407EF87849857"></a></p>
<h5>7.5-16 RotateList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RotateList</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Input: a list L</p>
<p>Output: a list L' which is the cyclic rotation of L (to the right)</p>
<table class="example">
<tr><td><pre>
gap> L:=[1,2,3,4];;
gap> RotateList(L);
[2,3,4,1]
</pre></td></tr></table>
<p><a id="X85E526367878F72A" name="X85E526367878F72A"></a></p>
<h5>7.5-17 CirculantMatrix</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CirculantMatrix</code>( <var class="Arg">k, L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Input: integer k, a list L of length n</p>
<p>Output: kxn matrix whose rows are cyclic rotations of the list L</p>
<table class="example">
<tr><td><pre>
gap> k:=3; L:=[1,2,3,4];;
gap> M:=CirculantMatrix(k,L);;
gap> Display(M);
</pre></td></tr></table>
<p><a id="X7969103F7A8598F9" name="X7969103F7A8598F9"></a></p>
<h4>7.6 <span class="Heading">
Miscellaneous polynomial functions
</span></h4>
<p>In this section we describe several multivariate polynomial GAP functions <strong class="pkg">GUAVA</strong> uses for constructing codes or performing calculations with codes.</p>
<p><a id="X84D51EBB784E7C5D" name="X84D51EBB784E7C5D"></a></p>
<h5>7.6-1 MatrixTransformationOnMultivariatePolynomial </h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MatrixTransformationOnMultivariatePolynomial </code>( <var class="Arg">AfR</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">A</var> is an nx n matrix with entries in a field F, <var class="Arg">R</var> is a polynomial ring of n variables, say F[x_1,...,x_n], and <var class="Arg">f</var> is a polynomial in <var class="Arg">R</var>. Returns the composition fcirc A.</p>
<p><a id="X80433A4B792880EF" name="X80433A4B792880EF"></a></p>
<h5>7.6-2 DegreeMultivariatePolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DegreeMultivariatePolynomial</code>( <var class="Arg">f, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This command takes two arguments, <var class="Arg">f</var>, a multivariate polynomial, and <var class="Arg">R</var> a polynomial ring over a field F containing <var class="Arg">f</var>, say R=F[x_1,x_2,...,x_n]. The output is simply the maximum degrees of all the monomials occurring in <var class="Arg">f</var>.</p>
<p>This command can be used to compute the degree of an affine plane curve.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);;
gap> R2:=PolynomialRing(F,2);
PolynomialRing(..., [ x_1, x_2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R2);;
gap> x:=vars[1];; y:=vars[2];;
gap> poly:=y^2-x*(x^2-1);;
gap> DegreeMultivariatePolynomial(poly,R2);
3
</pre></td></tr></table>
<p><a id="X83F44E397C56F2E0" name="X83F44E397C56F2E0"></a></p>
<h5>7.6-3 DegreesMultivariatePolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DegreesMultivariatePolynomial</code>( <var class="Arg">f, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a list of information about the multivariate polynomial <var class="Arg">f</var>. Nice for other programs but mostly unreadable by GAP users.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);;
gap> R2:=PolynomialRing(F,2);
PolynomialRing(..., [ x_1, x_2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R2);;
gap> x:=vars[1];; y:=vars[2];;
gap> poly:=y^2-x*(x^2-1);;
gap> DegreesMultivariatePolynomial(poly,R2);
[ [ [ x_1, x_1, 1 ], [ x_1, x_2, 0 ] ], [ [ x_2^2, x_1, 0 ], [ x_2^2, x_2, 2 ] ],
[ [ x_1^3, x_1, 3 ], [ x_1^3, x_2, 0 ] ] ]
gap>
</pre></td></tr></table>
<p><a id="X7E9021697A61A60F" name="X7E9021697A61A60F"></a></p>
<h5>7.6-4 CoefficientMultivariatePolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CoefficientMultivariatePolynomial</code>( <var class="Arg">f, var, power, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The command <code class="code">CoefficientMultivariatePolynomial</code> takes four arguments: a multivariant polynomial <var class="Arg">f</var>, a variable name <var class="Arg">var</var>, an integer <var class="Arg">power</var>, and a polynomial ring <var class="Arg">R</var> containing <var class="Arg">f</var>. For example, if <var class="Arg">f</var> is a multivariate polynomial in R = F[x_1,x_2,...,x_n] then <var class="Arg">var</var> must be one of the x_i. The output is the coefficient of x_i^power in <var class="Arg">f</var>.</p>
<p>(Not sure if F needs to be a field in fact ...)</p>
<p>Related to the GAP command <code class="code">PolynomialCoefficientsPolynomial</code>.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);;
gap> R2:=PolynomialRing(F,2);
PolynomialRing(..., [ x_1, x_2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R2);;
gap> x:=vars[1];; y:=vars[2];;
gap> poly:=y^2-x*(x^2-1);;
gap> PolynomialCoefficientsOfPolynomial(poly,x);
[ x_2^2, Z(11)^0, 0*Z(11), -Z(11)^0 ]
gap> PolynomialCoefficientsOfPolynomial(poly,y);
[ -x_1^3+x_1, 0*Z(11), Z(11)^0 ]
gap> CoefficientMultivariatePolynomial(poly,y,0,R2);
-x_1^3+x_1
gap> CoefficientMultivariatePolynomial(poly,y,1,R2);
0*Z(11)
gap> CoefficientMultivariatePolynomial(poly,y,2,R2);
Z(11)^0
gap> CoefficientMultivariatePolynomial(poly,x,0,R2);
x_2^2
gap> CoefficientMultivariatePolynomial(poly,x,1,R2);
Z(11)^0
gap> CoefficientMultivariatePolynomial(poly,x,2,R2);
0*Z(11)
gap> CoefficientMultivariatePolynomial(poly,x,3,R2);
-Z(11)^0
</pre></td></tr></table>
<p><a id="X79E76B6F7D177E27" name="X79E76B6F7D177E27"></a></p>
<h5>7.6-5 SolveLinearSystem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SolveLinearSystem</code>( <var class="Arg">L, vars</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Input: <var class="Arg">L</var> is a list of linear forms in the variables <var class="Arg">vars</var>.</p>
<p>Output: the solution of the system, if its unique.</p>
<p>The procedure is straightforward: Find the associated matrix A, find the "constant vector" b, and solve A*v=b. No error checking is performed.</p>
<p>Related to the GAP command <code class="code">SolutionMat( A, b )</code>.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);;
gap> R2:=PolynomialRing(F,2);
PolynomialRing(..., [ x_1, x_2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R2);;
gap> x:=vars[1];; y:=vars[2];;
gap> f:=3*y-3*x+1;; g:=-5*y+2*x-7;;
gap> soln:=SolveLinearSystem([f,g],[x,y]);
[ Z(11)^3, Z(11)^2 ]
gap> Value(f,[x,y],soln); # checking okay
0*Z(11)
gap> Value(g,[x,y],col); # checking okay
0*Z(11)
</pre></td></tr></table>
<p><a id="X80171AA687FFDC70" name="X80171AA687FFDC70"></a></p>
<h5>7.6-6 GuavaVersion</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GuavaVersion</code>( <var class="Arg"></var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the current version of Guava. Same as <code class="code">guava\_version()</code>.</p>
<table class="example">
<tr><td><pre>
gap> GuavaVersion();
"2.7"
</pre></td></tr></table>
<p><a id="X7EBBE86D85CC90C0" name="X7EBBE86D85CC90C0"></a></p>
<h5>7.6-7 ZechLog</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ZechLog</code>( <var class="Arg">x, b, F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the Zech log of x to base b, ie the i such that $x+1=b^i$, so $y+z=y(1+z/y)=b^k$, where k=Log(y,b)+ZechLog(z/y,b) and b must be a primitive element of F.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);; l := One(F);;
gap> ZechLog(2*l,8*l,F);
-24
gap> 8*l+l;(2*l)^(-24);
Z(11)^6
Z(11)^6
</pre></td></tr></table>
<p><a id="X7C8C1E6A7E3497F0" name="X7C8C1E6A7E3497F0"></a></p>
<h5>7.6-8 CoefficientToPolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CoefficientToPolynomial</code>( <var class="Arg">coeffs, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">CoefficientToPolynomial</code> returns the degree d-1 polynomial c_0+c_1x+...+c_d-1x^d-1, where <var class="Arg">coeffs</var> is a list of elements of a field, coeffs= c_0,...,c_d-1, and <var class="Arg">R</var> is a univariate polynomial ring.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);
GF(11)
gap> R1:=PolynomialRing(F,["a"]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
gap> coeffs:=Z(11)^0*[1,2,3,4];
[ Z(11)^0, Z(11), Z(11)^8, Z(11)^2 ]
gap> CoefficientToPolynomial(coeffs,R1);
Z(11)^2*a^3+Z(11)^8*a^2+Z(11)*a+Z(11)^0
</pre></td></tr></table>
<p><a id="X8431985183B63BB7" name="X8431985183B63BB7"></a></p>
<h5>7.6-9 DegreesMonomialTerm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DegreesMonomialTerm</code>( <var class="Arg">m, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">DegreesMonomialTerm</code> returns the list of degrees to which each variable in the multivariate polynomial ring <var class="Arg">R</var> occurs in the monomial <var class="Arg">m</var>, where <var class="Arg">coeffs</var> is a list of elements of a field.</p>
<table class="example">
<tr><td><pre>
gap> F:=GF(11);
GF(11)
gap> R1:=PolynomialRing(F,["a"]);;
gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
gap> b:=X(F,"b",var1);
b
gap> var2:=Concatenation(var1,[b]);
[ a, b ]
gap> R2:=PolynomialRing(F,var2);
PolynomialRing(..., [ a, b ])
gap> c:=X(F,"c",var2);
c
gap> var3:=Concatenation(var2,[c]);
[ a, b, c ]
gap> R3:=PolynomialRing(F,var3);
PolynomialRing(..., [ a, b, c ])
gap> m:=b^3*c^7;
b^3*c^7
gap> DegreesMonomialTerm(m,R3);
[ 0, 3, 7 ]
</pre></td></tr></table>
<p><a id="X860EF39B841380A1" name="X860EF39B841380A1"></a></p>
<h5>7.6-10 DivisorsMultivariatePolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DivisorsMultivariatePolynomial</code>( <var class="Arg">f, R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The function <code class="code">DivisorsMultivariatePolynomial</code> returns the list of polynomial divisors of <var class="Arg">f</var> in the multivariate polynomial ring <var class="Arg">R</var> with coefficients in a field. This program uses a simple but slow algorithm (see Joachim von zur Gathen, Jürgen Gerhard, <a href="chapBib.html#biBGG03">[GG03]</a>, exercise 16.10) which first converts the multivariate polynomial <var class="Arg">f</var> to an associated univariate polynomial f^*, then <code class="code">Factors</code> f^*, and finally converts these univariate factors back into the multivariate polynomial factors of <var class="Arg">f</var>. Since <code class="code">Factors</code> is non-deterministic, <code class="code">DivisorsMultivariatePolynomial</code> is non-deterministic as well.</p>
<table class="example">
<tr><td><pre>
gap> R2:=PolynomialRing(GF(3),["x1","x2"]);
PolynomialRing(..., [ x1, x2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R2);
[ x1, x2 ]
gap> x2:=vars[2];
x2
gap> x1:=vars[1];
x1
gap> f:=x1^3+x2^3;;
gap> DivisorsMultivariatePolynomial(f,R2);
[ x1+x2, x1+x2, x1+x2 ]
</pre></td></tr></table>
<p><a id="X82257DE97D1822AA" name="X82257DE97D1822AA"></a></p>
<h4>7.7 <span class="Heading">
GNU Free Documentation License
</span></h4>
<p>GNU Free Documentation License Version 1.2, November 2002</p>
<p>Copyright (C) 2000,2001,2002 Free Software Foundation, Inc. 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.</p>
<p>0. PREAMBLE</p>
<p>The purpose of this License is to make a manual, textbook, or other functional and useful document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others.</p>
<p>This License is a kind of "copyleft", which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software.</p>
<p>We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference.</p>
<p>1. APPLICABILITY AND DEFINITIONS</p>
<p>This License applies to any manual or other work, in any medium, that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. Such a notice grants a world-wide, royalty-free license, unlimited in duration, to use that work under the conditions stated herein. The "Document", below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as "you". You accept the license if you copy, modify or distribute the work in a way requiring permission under copyright law.</p>
<p>A "Modified Version" of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language.</p>
<p>A "Secondary Section" is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (Thus, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them.</p>
<p>The "Invariant Sections" are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License. If a section does not fit the above definition of Secondary then it is not allowed to be designated as Invariant. The Document may contain zero Invariant Sections. If the Document does not identify any Invariant Sections then there are none.</p>
<p>The "Cover Texts" are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License. A Front-Cover Text may be at most 5 words, and a Back-Cover Text may be at most 25 words.</p>
<p>A "Transparent" copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, that is suitable for revising the document straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup, or absence of markup, has been arranged to thwart or discourage subsequent modification by readers is not Transparent. An image format is not Transparent if used for any substantial amount of text. A copy that is not "Transparent" is called "Opaque".</p>
<p>Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML, PostScript or PDF designed for human modification. Examples of transparent image formats include PNG, XCF and JPG. Opaque formats include proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML, PostScript or PDF produced by some word processors for output purposes only.</p>
<p>The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text.</p>
<p>A section "Entitled XYZ" means a named subunit of the Document whose title either is precisely XYZ or contains XYZ in parentheses following text that translates XYZ in another language. (Here XYZ stands for a specific section name mentioned below, such as "Acknowledgements", "Dedications", "Endorsements", or "History".) To "Preserve the Title" of such a section when you modify the Document means that it remains a section "Entitled XYZ" according to this definition.</p>
<p>The Document may include Warranty Disclaimers next to the notice which states that this License applies to the Document. These Warranty Disclaimers are considered to be included by reference in this License, but only as regards disclaiming warranties: any other implication that these Warranty Disclaimers may have is void and has no effect on the meaning of this License.</p>
<p>2. VERBATIM COPYING</p>
<p>You may copy and distribute the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compensation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3.</p>
<p>You may also lend copies, under the same conditions stated above, and you may publicly display copies.</p>
<p>3. COPYING IN QUANTITY</p>
<p>If you publish printed copies (or copies in media that commonly have printed covers) of the Document, numbering more than 100, and the Document's license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects.</p>
<p>If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages.</p>
<p>If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a computer-network location from which the general network-using public has access to download using public-standard network protocols a complete Transparent copy of the Document, free of added material. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public.</p>
<p>It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document.</p>
<p>4. MODIFICATIONS</p>
<p>You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you release the Modified Version under precisely this License, with the Modified Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version:</p>
<p>A. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous versions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission.</p>
<p>B. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has fewer than five), unless they release you from this requirement.</p>
<p>C. State on the Title page the name of the publisher of the Modified Version, as the publisher.</p>
<p>D. Preserve all the copyright notices of the Document.</p>
<p>E. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices.</p>
<p>F. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Addendum below.</p>
<p>G. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Document's license notice.</p>
<p>H. Include an unaltered copy of this License.</p>
<p>I. Preserve the section Entitled "History", Preserve its Title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section Entitled "History" in the Document, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sentence.</p>
<p>J. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for previous versions it was based on. These may be placed in the "History" section. You may omit a network location for a work that was published at least four years before the Document itself, or if the original publisher of the version it refers to gives permission.</p>
<p>K. For any section Entitled "Acknowledgements" or "Dedications", Preserve the Title of the section, and preserve in the section all the substance and tone of each of the contributor acknowledgements and/or dedications given therein.</p>
<p>L. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equivalent are not considered part of the section titles.</p>
<p>M. Delete any section Entitled "Endorsements". Such a section may not be included in the Modified Version.</p>
<p>N. Do not retitle any existing section to be Entitled "Endorsements" or to conflict in title with any Invariant Section.</p>
<p>O. Preserve any Warranty Disclaimers.</p>
<p>If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles.</p>
<p>You may add a section Entitled "Endorsements", provided it contains nothing but endorsements of your Modified Version by various parties--for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard.</p>
<p>You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one.</p>
<p>The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version.</p>
<p>5. COMBINING DOCUMENTS</p>
<p>You may combine the Document with other documents released under this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invariant Sections of all of the original documents, unmodified, and list them all as Invariant Sections of your combined work in its license notice, and that you preserve all their Warranty Disclaimers.</p>
<p>The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work.</p>
<p>In the combination, you must combine any sections Entitled "History" in the various original documents, forming one section Entitled "History"; likewise combine any sections Entitled "Acknowledgements", and any sections Entitled "Dedications". You must delete all sections Entitled "Endorsements".</p>
<p>6. COLLECTIONS OF DOCUMENTS</p>
<p>You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects.</p>
<p>You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document.</p>
<p>7. AGGREGATION WITH INDEPENDENT WORKS</p>
<p>A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of a storage or distribution medium, is called an "aggregate" if the copyright resulting from the compilation is not used to limit the legal rights of the compilation's users beyond what the individual works permit. When the Document is included in an aggregate, this License does not apply to the other works in the aggregate which are not themselves derivative works of the Document.</p>
<p>If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one half of the entire aggregate, the Document's Cover Texts may be placed on covers that bracket the Document within the aggregate, or the electronic equivalent of covers if the Document is in electronic form. Otherwise they must appear on printed covers that bracket the whole aggregate.</p>
<p>8. TRANSLATION</p>
<p>Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License, and all the license notices in the Document, and any Warranty Disclaimers, provided that you also include the original English version of this License and the original versions of those notices and disclaimers. In case of a disagreement between the translation and the original version of this License or a notice or disclaimer, the original version will prevail.</p>
<p>If a section in the Document is Entitled "Acknowledgements", "Dedications", or "History", the requirement (section 4) to Preserve its Title (section 1) will typically require changing the actual title.</p>
<p>9. TERMINATION</p>
<p>You may not copy, modify, sublicense, or distribute the Document except as expressly provided for under this License. Any other attempt to copy, modify, sublicense or distribute the Document is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance.</p>
<p>10. FUTURE REVISIONS OF THIS LICENSE</p>
<p>The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. See http://www.gnu.org/copyleft/.</p>
<p>Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap6.html">Previous Chapter</a> <a href="chapBib.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
1814
