Namespaces
Variants
Actions

Difference between revisions of "User:Richard Pinch/sandbox-CZ"

From Encyclopedia of Mathematics
Jump to: navigation, search
 
(15 intermediate revisions by the same user not shown)
Line 1: Line 1:
  
  
=Justesen code=
 
A class of [[error-correcting code]]s which are derived from [[Reed-Solomon code]]s and have good error-control properties.
 
 
Let $R$ be a Reed-Solomon code of length $N = 2^m-1$, [[dimension (vector space)|rank]] $K$ and minimum weight $N-K+1$.  The symbols of $R$ are elements of $F=GF(2^m)$ and the codewords are obtained by taking every polynomial $f$ over $F$ of degree less than $K$ and listing the values of $f$ on the non-zero elements of $F$ in some predetermined order.  Let $\alpha$ be a [[Primitive element of a Galois field|primitive element]] of $F$.  For a codeword $\mathbf{a} = (a_1,\ldots,a_N)$ from $R$, let $\mathbf{b}$ be the vector of length $2N$ over $F$ given by
 
$$
 
\mathbf{b} = \left( a_1, a_1, a_2, \alpha^1 a_2, \ldots, a_N, \alpha^{N-1} a_N \right)
 
$$
 
and let $\mathbf{c}$ be the vector of length $2Nm$ obtained from $\mathbf{b}$ by expressing each element of $F$ as a binary vector of length $m$.  The ''Justesen code'' is the linear code containing all such $\mathbf{c}$.
 
 
The parameters of this code are length $2mN$, dimension $mK$ and minimum distance at least
 
$$
 
\sum_{i=1}^l i \binom{2m}{i} \ .
 
$$
 
The Justesen codes are examples of [[concatenated code]]s.
 
 
== References ==
 
* {{User:Richard Pinch/sandbox/Ref | author=J. Justesen | title=A class of constructive asymptotically good algebraic codes | journal=IEEE Trans. Info. Theory | volume=18 | year=1972 | pages=652-656 }}
 
* {{User:Richard Pinch/sandbox/Ref | author=F.J. MacWilliams | authorlink=Jessie MacWilliams | coauthors=N.J.A. Sloane | title=The Theory of Error-Correcting Codes | publisher=North-Holland | date=1977 | isbn=0-444-85193-3 | pages=306-316 }}
 
 
=Monogenic field=
 
 
An [[algebraic number field]] for which there exists an element
 
$\alpha$ such that the [[ring of integers]] $O_K$ is a polynomial ring $\mathbb{Z}[\alpha]$.  The powers of such a element $\alpha$ constitute a '''power integral basis'''.
 
 
In a monogenic field $K$, the [[Discriminant of an algebraic number field|field discriminant]] of $K$ is equal to the [[discriminant of a polynomial|discriminant]] of the [[Minimal polynomial (field theory)|minimal polynomial]] of $\alpha$.
 
 
Examples of monogenic fields include:
 
* [[Quadratic field]]s: if $K = \mathbf{Q}(\sqrt d)$ with $d$ a [[square-free integer]] then $O_K = \mathbf{Z}[\alpha]$ where $\alpha = (1+\sqrt d)/2$ if $d \equiv 1 \pmod 4$ and $\alpha = \sqrt d$ otherwise.
 
* [[Cyclotomic field]]s: if $K = \mathbf{Q}(\zeta)$ with $\zeta$ a root of unity, then $O_K = \mathbf{Z}[\zeta]$.
 
 
Not all number fields are monogenic: Dirichlet gave the example of the [[cubic field]] generated by a root of the polynomial $X^3 - X^2 - 2X - 8$.
 
 
==References==
 
* {{User:Richard Pinch/sandbox/Ref | last = Narkiewicz | first = Władysław | title = Elementary and Analytic Theory of Algebraic Numbers | publisher = [[Springer-Verlag]] | year = 2004 | pages = 64 | isbn = 3540219021}}
 
 
=Moore determinant=
 
A [[determinant]], named after [[E. H. Moore]], defined over a [[finite field]] from a square '''Moore [[matrix]]'''.  A Moore matrix has successive powers of the [[Frobenius automorphism]] applied to the first column, i.e., an $m \times n$
 
$$
 
M=\begin{bmatrix}
 
\alpha_1 & \alpha_1^q & \dots & \alpha_1^{q^{n-1}}\\
 
\alpha_2 & \alpha_2^q & \dots & \alpha_2^{q^{n-1}}\\
 
\alpha_3 & \alpha_3^q & \dots & \alpha_3^{q^{n-1}}\\
 
\vdots & \vdots & \ddots &\vdots \\
 
\alpha_m & \alpha_m^q & \dots & \alpha_m^{q^{n-1}}\\
 
\end{bmatrix}
 
$$
 
or
 
$$
 
M_{i,j} = \alpha_i^{q^{j-1}}
 
$$
 
for all indices $i$ and $j$. (Some authors use the [[transpose]] of the above matrix.)
 
 
The Moore determinant of a square Moore matrix (so $m=n$) can be expressed as:
 
$$
 
\det(V) = \prod_{\mathbf{c}} \left( c_1\alpha_1 + \cdots c_n\alpha_n \right) \,,
 
$$
 
where $c$ runs over a complete set of direction vectors, made specific by having the last non-zero entry equal to 1.
 
 
==See also==
 
* [[Alternant matrix]]
 
* [[Vandermonde determinant]]
 
* [[List of matrices]]
 
 
==References==
 
* {{User:Richard Pinch/sandbox/Ref | author=David Goss | title=Basic Structures of Function Field Arithmetic | date=1996 | publisher=Springer Verlag | isbn=3-540-63541-6}}  Chapter 1.
 
 
 
 
=Morita conjectures=
 
The '''Morita conjectures''' in [[topology]] ask
 
 
# If ''X'' × ''Y'' is [[normal space|normal]] for every normal space ''Y'', is ''X'' [[discrete space|discrete]]?
 
# If ''X'' &times; ''Y'' is normal for every normal P-space ''Y'', is ''X'' [[metrizable]] <ref>K. Morita,  "Some problems on normality of products of spaces"  J. Novák (ed.) , Proc. Fourth Prague Topological Symp. (Prague, August 1976) , Soc. Czech. Math. and Physicists , Prague  (1977)  pp. 296–297</ref>?
 
# If ''X'' &times; ''Y'' is normal for every normal countably [[paracompact]] space ''Y'', is ''X'' metrizable and [[sigma-locally compact]]?
 
 
Here a '''normal P-space''' ''Y'' is characterised by the property that the product with every metrizable ''X'' is normal; it is thus conjectured that the converse holds.
 
 
K. Chiba, T.C. Przymusiński and [[Mary Ellen Rudin|M.E. Rudin]]
 
<ref>K. Chiba,  T.C. Przymusiński,  M.E. Rudin,  "Normality of products and Morita's conjectures"  ''Topol. Appl.'' '''22'''  (1986)  19–32</ref> proved conjecture (1) and showed that conjecture (2) is true if the [[axiom of constructibility]] ''V=L'', holds.
 
 
[[Zoltán Tibor Balogh|Z. Balogh]] proved conjectures (2) and (3)<ref>Z. Balogh, Non-shrinking open covers and K. Morita's duality conjectures, ''Topology Appl.'', '''115''' (2001) 333-341</ref>.
 
 
==References==
 
<references/>
 
* A.V. Arhangelskii, K.R. Goodearl, B. Huisgen-Zimmermann, ''Kiiti Morita 1915-1995'', Notices of the AMS, June 1997 [http://www.ams.org/notices/199706/morita.pdf]
 
 
 
=Partition function (number theory)=
 
The function $p(n)$ that counts the number of [[partition]]s of a positive integer $n$, that is, the number of ways of expressing $n$ as a sum of positive integers (where order is not significant).
 
 
Thus ''p''(3) = 3, since the number 3 has 3 partitions:
 
* $3$
 
* $2+1$
 
* $1+1+1$
 
 
The partition function satisfies an asymptotic relation
 
$$
 
p(n) \sim \frac{\exp\left(\pi\sqrt{2/3}\sqrt n\right)}{4n\sqrt3} \ .
 
$$
 
 
==References==
 
* {{User:Richard Pinch/sandbox/Ref  | author=Tom M. Apostol | title=Modular functions and Dirichlet Series in Number Theory  | edition=2nd ed | series=[[Graduate Texts in Mathematics]] | volume=41 | publisher=[[Springer-Verlag]] | year=1990 | isbn=0-387-97127-0 | pages=94-112 }}
 
* {{User:Richard Pinch/sandbox/Ref  | author=G.H. Hardy | authorlink=G. H. Hardy | coauthors=[[E. M. Wright]] | title=An Introduction to the Theory of Numbers | edition=6th ed. | publisher=[[Oxford University Press]] | year=2008 | isbn=0-19-921986-5 | pages=361-392 }}
 
 
=Preparata code=
 
 
A class of non-linear double-[[error-correcting code]]s.  They are named after [[Franco P. Preparata]] who first described them in 1968.
 
 
Let ''m'' be an odd number,  and ''n'' = 2<sup>''m''</sup>-1.  We first describe the '''extended Preparata code''' of length 2''n''+2 = 2<sup>''m''+1</sup>: the Preparata code is then derived by deleting one position.  The words of the extended code are regarded as pairs (''X'',''Y'') of 2<sup>''m''</sup>-tuples, each corresponding to subsets of the [[finite field]] GF(2<sup>''m''</sup>) in some fixed way.
 
 
The extended code contains the words (''X'',''Y'') satisfying three conditions
 
 
# ''X'', ''Y'' each have even weight;
 
# <math>\sum_{x \in X} x = \sum_{y \in Y} y</math>;
 
# <math>\sum_{x \in x} x^3 + \left(\sum_{x \in X} x\right)^3 = \sum_{y \in Y} y^3</math>.
 
 
The Peparata code is obtained by deleting the position in ''X'' corresponding to 0 in GF(2<sup>''m''</sup>).
 
 
The Preparata code is of length 2<sup>''m''+1</sup>-1, size 2<sup>''k''</sup> where ''k'' = 2<sup>''m''+1</sup> - 2''m'' - 2, and minimum distance 5.
 
 
When ''m''=3, the Preparata code of length 15 is also called the '''Nordstrom–Robinson code'''.
 
 
== References ==
 
* {{User:Richard Pinch/sandbox/Ref | author=F.P. Preparata | authorlink=Franco P. Preparata | title=A class of optimum nonlinear double-error-correcting codes | journal=Information and Control | volume=13 | year=1968 | pages=378-400 | doi=10.1016/S0019-9958(68)90874-7 }}
 
* {{User:Richard Pinch/sandbox/Ref | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd ed | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | date=1992 | isbn=3-540-54894-7 | pages=111-113}}
 
 
=Selberg sieve=
 
=Selberg sieve=
 
A technique for estimating the size of "sifted sets" of [[positive integer]]s which satisfy a set of conditions which are expressed by [[Congruence relation#Modular arithmetic|congruence]]s.  It was developed by [[Atle Selberg]] in the 1940s.
 
A technique for estimating the size of "sifted sets" of [[positive integer]]s which satisfy a set of conditions which are expressed by [[Congruence relation#Modular arithmetic|congruence]]s.  It was developed by [[Atle Selberg]] in the 1940s.
Line 209: Line 84:
 
==References==
 
==References==
 
* {{User:Richard Pinch/sandbox/Ref | last1=Steen | first1=Lynn Arthur | last2=Seebach | first2=J. Arthur Jr. | title=Counterexamples in Topology | year=1978 | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=0-387-90312-7 }}
 
* {{User:Richard Pinch/sandbox/Ref | last1=Steen | first1=Lynn Arthur | last2=Seebach | first2=J. Arthur Jr. | title=Counterexamples in Topology | year=1978 | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=0-387-90312-7 }}
 
=Stably free module=
 
In [[mathematics]], a '''stably free module''' is a [[module (mathematics)|module]] which is close to being [[free module|free]].
 
 
==Definition==
 
A module ''M'' over a ring ''R'' is ''stably free'' if there exist free modules ''F'' and ''G'' over ''R'' such that
 
 
:<math> M \oplus F = G . \, </math>
 
 
==Properties==
 
* A module is stably free if and only if it possesses a finite [[free resolution]].
 
 
== See also ==
 
* [[Free object]]
 
 
==References==
 
* {{User:Richard Pinch/sandbox/Ref | author=Serge Lang | authorlink=Serge Lang | title=Algebra | edition=3rd ed. | publisher=[[Addison-Wesley]] | year=1993 | isbn=0-201-55540-9 | page=840}}
 
 
 
=Tau function=
 
In [[mathematics]], Ramanujan's '''tau function''' is an [[arithmetic function]] which may defined in terms of the [[Delta form]] by the formal infinite product
 
 
:<math>q \prod_{n=1}^\infty \left(1-q^n\right)^{24} = \sum_n \tau(n) q^n .\,</math>
 
 
Since Δ is a [[Hecke operator|Hecke]] [[eigenform]], the tau function is multiplicative, with [[formal Dirichlet series]] and Euler product
 
 
:<math> \sum_n \tau(n) n^{-s} = \prod_p \left(1 - \tau(p) p^{-s} + p^{11-2s} \right)^{-1} .\,</math>
 
 
  
 
=Turan sieve=
 
=Turan sieve=
Line 272: Line 119:
 
==References==
 
==References==
 
* {{cite book | author=Alina Carmen Cojocaru | coauthors=M. Ram Murty | title=An introduction to sieve methods and their applications | series=London Mathematical Society Student Texts | volume=66 | publisher=[[Cambridge University Press]] | isbn=0-521-61275-6 | pages=47-62 }}
 
* {{cite book | author=Alina Carmen Cojocaru | coauthors=M. Ram Murty | title=An introduction to sieve methods and their applications | series=London Mathematical Society Student Texts | volume=66 | publisher=[[Cambridge University Press]] | isbn=0-521-61275-6 | pages=47-62 }}
=Tutte matrix=
 
In [[graph theory]], the '''Tutte matrix''' <math>A</math> of a [[Graph (mathematics)|graph]] ''G'' = (''V'',''E'') is a matrix used to determine the existence of a [[perfect matching]]: that is, a set of edges which is incident with each vertex exactly once.
 
 
If the set of vertices ''V'' has 2''n'' elements then the Tutte matrix is a 2''n'' × 2''n'' matrix A with entries
 
 
::: <math>A_{ij} = \begin{cases} x_{ij}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i<j\\
 
-x_{ji}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i>j\\
 
0\;\;\;\;\mbox{otherwise} \end{cases}</math>
 
 
where the ''x''<sub>''ij''</sub> are indeterminates.  The [[determinant]] of this [[skew-symmetric]] matrix is then a polynomial (in the variables ''x<sub>ij</sub>'', ''i<j'' ): this coincides with the square of the [[pfaffian]] of the matrix ''A'' and is non-zero (as a polynomial) if and only if a perfect matching exists.  (It should be noted that this is not the [[Tutte polynomial]] of ''G''.)
 
 
The Tutte matrix is a generalisation of the [[Edmonds matrix]] for a balanced [[bipartite graph]].
 
 
==References==
 
*{{cite book|author=R. Motwani, P. Raghavan |title=Randomized Algorithms|publisher=Cambridge University Press|year=1995|page=167}}
 
*{{cite book|author=Allen B. Tucker|title=Computer Science Handbook|publisher=CRC Press|date=2004|isbn=158488360X|page=12.19}}
 
* {{cite journal|url= http://jlms.oxfordjournals.org/cgi/reprint/s1-22/2/107.pdf|title= The factorization of linear graphs.
 
|accessdate= 2008-06-15|author= W.T. Tutte|authorlink=W. T. Tutte|year= 1947|month= April|volume=22|journal=J. London Math. Soc.|pages=107-111|doi=10.1112/jlms/s1-22.2.107}}
 
 
 
 
=Weierstrass preparation theorem=
 
=Weierstrass preparation theorem=
 
In [[algebra]], the '''Weierstrass preparation theorem''' describes a canonical form for [[formal power series]] over a [[complete local ring]].
 
In [[algebra]], the '''Weierstrass preparation theorem''' describes a canonical form for [[formal power series]] over a [[complete local ring]].

Latest revision as of 19:14, 2 May 2020


Selberg sieve

A technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Atle Selberg in the 1940s.

Description

In terms of sieve theory the Selberg sieve is of combinatorial type: that is, derives from a careful use of the inclusion-exclusion principle. Selberg replaced the values of the Möbius function which arise in this by a system of weights which are then optimised to fit the given problem. The result gives an upper bound for the size of the sifted set.

Let A be a set of positive integers ≤ x and let P be a set of primes. For each p in P, let Ap denote the set of elements of A divisible by p and extend this to let Ad the intersection of the Ap for p dividing d, when d is a product of distinct primes from P. Further let A1 denote A itself. Let z be a positive real number and P(z) denote the product of the primes in P which are ≤ z. The object of the sieve is to estimate

\[S(A,P,z) = \left\vert A \setminus \bigcup_{p \in P(z)} A_p \right\vert . \]

We assume that |Ad| may be estimated by

\[ \left\vert A_d \right\vert = \frac{1}{f(d)} X + R_d . \]

where f is a multiplicative function and X   =   |A|. Let the function g be obtained from f by Möbius inversion, that is

\[ g(n) = \sum_{d \mid n} \mu(d) f(n/d) \] \[ f(n) = \sum_{d \mid n} g(d) \]

where μ is the Möbius function. Put

\[ V(z) = \sum_{\begin{smallmatrix}d < z \\ d \mid P(z)\end{smallmatrix}} \frac{\mu^2(d)}{g(d)} . \]

Then

\[ S(A,P,z) \le \frac{X}{V(z)} + O\left({\sum_{\begin{smallmatrix} d_1,d_2 < z \\ d_1,d_2 \mid P(z)\end{smallmatrix}} \left\vert R_{[d_1,d_2]} \right\vert} \right) .\]

It is often useful to estimate V(z) by the bound

\[ V(z) \ge \sum_{d \le z} \frac{1}{f(d)} . \, \]

Applications

  • The Brun-Titchmarsh theorem on the number of primes in an arithmetic progression;
  • The number of nx such that n is coprime to φ(n) is asymptotic to e x / log log log (x) .

References

  • Alina Carmen Cojocaru; M. Ram Murty; An introduction to sieve methods and their applications, ser. London Mathematical Society Student Texts 66 , pp. 113-134, Cambridge University Press ISBN: 0-521-61275-6
  • George Greaves; Sieves in number theory, , Springer-Verlag ISBN: 3-540-41647-1
  • Heini Halberstam; H.E. Richert; Sieve Methods, , Academic Press ISBN: 0-12-318250-6
  • Christopher Hooley; Applications of sieve methods to the theory of numbers, , pp. 7-12, Cambridge University Press ISBN: 0-521-20915-3
  • Atle Selberg; On an elementary method in the theory of primes, Norske Vid. Selsk. Forh. Trondheim, 19 (1947), pp. 64-67

Separation axioms

In topology, separation axioms describe classes of topological space according to how well the open sets of the topology distinguish between distinct points.


Terminology

A neighbourhood of a point x in a topological space X is a set N such that x is in the interior of N; that is, there is an open set U such that \(x \in U \subseteq N\). A neighbourhood of a set A in X is a set N such that A is contained in the interior of N; that is, there is an open set U such that \(A \subseteq U \subseteq N\).

Subsets U and V are separated in X if U is disjoint from the closure of V and V is disjoint from the closure of U.

A Urysohn function for subsets A and B of X is a continuous function f from X to the real unit interval such that f is 0 on A and 1 on B.

Axioms

A topological space X is

  • T0 if for any two distinct points there is an open set which contains just one
  • T1 if for any two points x, y there are open sets U and V such that U contains x but not y, and V contains y but not x
  • T2 if any two distinct points have disjoint neighbourhoods
  • T2½ if distinct points have disjoint closed neighbourhoods
  • T3 if a closed set A and a point x not in A have disjoint neighbourhoods
  • T3½ if for any closed set A and point x not in A there is a Urysohn function for A and {x}
  • T4 if disjoint closed sets have disjoint neighbourhoods
  • T5 if separated sets have disjoint neighbourhoods
  • Hausdorff is a synonym for T2
  • completely Hausdorff is a synonym for T2½
  • regular if T0 and T3
  • completely regular if T0 and T3½
  • Tychonoff is completely regular and T1
  • normal if T0 and T4
  • completely normal if T1 and T5
  • perfectly normal if normal and every closed set is a Gδ

Properties

  • A space is T1 if and only if each point (singleton) forms a closed set.
  • Urysohn's Lemma: if A and B are disjoint closed subsets of a T4 space X, there is a Urysohn function for A and B'.

References

  • Steen, Lynn Arthur; Seebach, J. Arthur Jr.; Counterexamples in Topology, (1978), Springer-Verlag ISBN: 0-387-90312-7

Turan sieve

In mathematics, in the field of number theory, the Turán sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Pál Turán in 1934.

Description

In terms of sieve theory the Turán sieve is of combinatorial type: deriving from a rudimentary form of the inclusion-exclusion principle. The result gives an upper bound for the size of the sifted set.

Let A be a set of positive integers ≤ x and let P be a set of primes. For each p in P, let Ap denote the set of elements of A divisible by p and extend this to let Ad the intersection of the Ap for p dividing d, when d is a product of distinct primes from P. Further let A1 denote A itself. Let z be a positive real number and P(z) denote the product of the primes in P which are ≤ z. The object of the sieve is to estimate

\[S(A,P,z) = \left\vert A \setminus \bigcup_{p \in P(z)} A_p \right\vert . \]

We assume that |Ad| may be estimated, when d is a prime p by

\[ \left\vert A_p \right\vert = \frac{1}{f(p)} X + R_p \]

and when d is a product of two distinct primes d = p q by

\[ \left\vert A_{pq} \right\vert = \frac{1}{f(p)f(q)} X + R_{p,q} \]

where X   =   |A| and f is a function with the property that 0 ≤ f(d) ≤ 1. Put

\[ U(z) = \sum_{p \mid P(z)} f(p) . \]

Then

\[ S(A,P,z) \le \frac{X}{U(z)} + \frac{2}{U(z)} \sum_{p \mid P(z)} \left\vert R_p \right\vert + \frac{1}{U(z)^2} \sum_{p,q \mid P(z)} \left\vert R_{p,q} \right\vert . \]

Applications

References

Weierstrass preparation theorem

In algebra, the Weierstrass preparation theorem describes a canonical form for formal power series over a complete local ring.

Let O be a complete local ring and f a formal power series in O''X''. Then f can be written uniquely in the form

\[f = (X^n + b_{n-1}X^{n-1} + \cdots + b_0) u(x) , \,\]

where the bi are in the maximal ideal m of O and u is a unit of O''X''.

The integer n defined by the theorem is the Weierstrass degree of f.

References

  • Serge Lang; Algebra, (1993), pp. 208-209, Addison-Wesley ISBN: 0-201-55540-9


Zipf distribution

In probability theory and statistics, the Zipf distribution and zeta distribution refer to a class of discrete probability distributions. They have been used to model the distribution of words in words in a text , of text strings and keys in databases, and of the sizes of businesses and towns.

The Zipf distribution with parameter n assigns probability proportional to 1/r to an integer rn and zero otherwise, with normalization factor Hn, the n-th harmonic number.

A Zipf-like distribution with parameters n and s assigns probability proportional to 1/rs to an integer rn and zero otherwise, with normalization factor \(\sum_{r=1}^n 1/r^s\).

The zeta distribution with parameter s assigns probability proportional to 1/rs to all integers r with normalization factor given by the Riemann zeta function 1/ζ(s).

References

How to Cite This Entry:
Richard Pinch/sandbox-CZ. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-CZ&oldid=34710