Wikipedia - Benutzerbeiträge [de]

Steinhaus-Johnson-Trotter-Algorithmus

2005-12-13T03:11:49Z

Mathbot: Internal link to cut-the-knot. See talk:cut-the-knot for discussion and comments. This is a semi-automatic update.

The '''Steinhaus-Johnson-Trotter algorithm''' or '''Johnson-Trotter algorithm''' is an [[algorithm]] which generates [[permutation]]s by transposing elements.

==See also==
* [[Fisher-Yates shuffle]]

==External links==
* [http://www.theory.csc.uvic.ca/%7Ecos/inf/perm/PermInfo.html Implentation of the Steinhaus-Johnson-Trotter algorithm]
* [http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml Counting And Listing All Permutations: Johnson-Trotter Method] at [[cut-the-knot]]

==References==
* {{DADS|Johnson-Trotter|johnsonTrotter}}

{{comp-sci-stub}}
{{Combin-stub}}

[[Category:Combinatorial algorithms]]

LeGrand Richards

2005-11-10T03:41:16Z

Mathbot: Put space after period and comma as per typographical rules in English. This is a semiautomatic update.

'''LeGrand Richards''' ([[February 6]], [[1886]]–[[January 11]], [[1983]]) was Presiding Bishop of [[Church of Jesus Christ of Latter-day Saints|The Church of Jesus Christ of Latter-day Saints]] from [[1938]] to [[1952]], and then a member of the [[Quorum of the Twelve Apostles]] until his death. He was the longest-lived [[Apostle (Mormonism)|Apostle]] until [[David B. Haight]]. Both his father [[George F. Richards]] and grandfather [[Franklin D. Richards]] had served as [[President of the Quorum of the Twelve Apostles]]. Franklin D. was also the nephew of [[Willard Richards]], another notable member of LDS church history and [[Apostle (Mormonism)|Apostle]].

==References==

{{Web reference_author | Author=D. Michael Quinn | Title=They Served: The Richards Legacy in the Church | Work=Ensign | URL=http://library.lds.org/nxt/gateway.dll/Magazines/Ensign/1980.htm/ensign%20january%201980.htm/they%20served%20the%20richards%20legacy%20in%20the%20church%20.htm?f=templates$fn=default.htm$3.0 | Date=09 12 | Year=2005}}

{{start box}}
{{series box |
title= [[Quorum of the Twelve Apostles]] |
years= [[April 10]], [[1952]]–[[January 11]], [[1983]] |
before=[[Marion G. Romney]] |
after= [[Adam S. Bennion]] |
}}
{{end box}}

[[Category:1886 births|Richards, LeGrand]]
[[Category:1983 deaths|Richards, LeGrand]]
[[Category:Apostles of the Church of Jesus Christ of Latter-day Saints|Richards, LeGrand]]
[[Category:Latter Day Saints|Richards, LeGrand]]
[[Category:Latter Day Saint leaders|Richards, LeGrand]]
{{LDS-stub}}

Benutzer:Tino Cannst/Minkowski'schen Fragezeichenfunktion

2005-10-20T12:19:52Z

Mathbot: Robot-assisted spelling. See User:Mathbot/Logged misspellings for changes.

In [[mathematics]], the '''Minkowski question mark function''', sometimes called the '''slippery devil's staircase''', is a [[Function (mathematics)|function]], denoted ?(''x''), possessing various unusual fractal properties. It was defined by [[Hermann Minkowski]] in [[1904]] by matching the [[quadratic irrational]]s to the [[dyadic rational]]s on the unit interval. The expression relating continued fractions to the dyadics (as commonly used, and defined below) was given by [[Arnaud Denjoy]] in [[1938]].

[[Image:Minkowski question mark.svg|300px|right|Minkowski question mark function]]
==Definition==
If <math>[a_0; a_1, a_2, \ldots]</math> is the [[continued fraction|continued fraction representation]] of an [[irrational number]] ''x'', then

:<math>{\rm ?}(x) = a_0 + 2 \sum_{n=1}^\infty (-1)^{n+1}2^{-a_1 - \cdots -a_n}</math>

whereas:

If <math>[a_0; a_1, a_2, \ldots a_m]</math> is a continued fraction representation of a [[rational number]], then

:<math>{\rm ?}(x) = a_0 + 2 \sum_{n=1}^m (-1)^{n+1}2^{-a_1 - \cdots -a_n}</math>

It should be noted that if <math>a_m>1</math> then
<math>[a_0; a_1, a_2, \ldots a_m-1, 1]</math> is also a continued fraction for the same number, but the two expressions give identical values for ?(''x'').

For rational numbers the function may also be defined recursively; if ''p/q'' and ''r/s'' are reduced fractions such that |''ps'' − ''rq''| = 1 (so that they are adjacent elements of a row of the [[Farey sequence]]) then

:<math>?\left(\frac{p+r}{q+s}\right) = \frac12 \left(?\bigg(\frac pq\bigg) + ?\bigg(\frac rs\bigg)\right)</math>

Note that in general, any [[Matrix (mathematics)|matrix]] <math>\begin{pmatrix} p & q \\ r & s \end{pmatrix}</math> having unit determinant is by definition a member of the [[modular group]]. The question mark function is self-similar, with the [[modular group]] describing the self-similarity. This follows in part because if <math>p_{n-1}/q_{n-1}</math> and <math>p_{n}/q_{n}</math> are two successive convergents of a [[continued fraction]], then the matrix
<math>\begin{pmatrix} p_{n-1} & p_{n} \\ q_{n-1} & q_{n} \end{pmatrix}</math>
has [[determinant]] ±1.

To get some intuition for the definition above,
let's consider two different ways
of interpreting an infinite string of bits beginning with 0 as a real number in [0,1].
One obvious way to interpret such a string is to place a binary point after the first 0 and read the string as a [[binary numeral system|binary]] expansion: thus, for instance, the string 001001001001001001001001...
represents the binary number 0.010010010010..., or 2/7. Another interpretation
views a string as the [[continued fraction]] [0;''a''1,''a''2,...], where the integers ''a''i are the run lengths in a [[run-length encoding]] of the string. The same example string 001001001001001001001001... then
corresponds to [0;2,1,2,1,2,1,...] = (√3-1)/2. (If the string ends in an infinitely long run of the same bit, we ignore it and terminate the representation; this is suggested by the formal "identity" [0;''a''1,...,''a''n,∞]=[0;''a''1,...,''a''n+1/∞]=
[0;''a''1,...,''a''n+0]=[0;''a''1,...,''a''n].)

The effect of the question mark function on [0,1] can then be understood as mapping the second interpretation of a string to the first interpretation of the same string. Our example string gives the equality
:<math>?\left(\frac{\sqrt3-1}{2}\right)=\frac{2}{7}.</math>

==Properties of ?(''x'')==

The question mark function is a strictly increasing and [[absolutely continuous]] function. The [[derivative]] vanishes on the [[rational number]]s; however, since the rationals are a set of [[measure zero]], this vanishing of the derivative at the rationals is not in contradiction with the continuity of the function. It does not have a well-defined derivative, in the classical sense, on the irrationals; however, there are several constructions for a [[measure (mathematics)|measure]] that, when integrated, yields the question mark function. One such construction is obtained by measuring the density of the [[Farey sequence|Farey numbers]] on the real number line. The question mark measure is the prototypical example of what are sometimes referred to as [[multi-fractal measure]]s.

The question mark function sends rational numbers to [[dyadic rational|dyadic rational number]]s, meaning those whose [[Binary numeral system|base two]] representation terminates. It sends [[quadratic irrational]]s to non-dyadic rational numbers. It is an [[odd function]], and satisfies the functional equation ?(''x'' + 1) = ?(''x'') + 1; consequently ''x''→?(''x'') − ''x'' is an odd periodic function with period one. If ?(''x'') is irrational, then ''x'' is either [[algebraic number|algebraic]] of degree greater than two, or [[transcendental number|transcendental]]. The function is invertible, and the [[inverse function]] has also attracted the attention of various mathematicians, in particular [[John Conway]], whose notation for ?−1(''x'') is ''x'' with a box drawn around it.

The Minkowski question mark function is a special case of fractal curves known as [[de Rham curve]]s.

==Historical references==
* H. Minkowski, ''Verhandlungen des iii internationalen mathematiker-kongresses in heidelberg'', (1904) Berlin.
* A. Denjoy, ''Sur une fonction reelle de Minkowski'', J. Math. Pures Appl. '''17''' (1938) p105-151.

==References==
* Biblioni, L., Paradis, J., Viader, P., ''[http://www.econ.upf.es/eng/research/onepaper.php?id=226 A New Light on Minkowski's ?(x) Function]'', Journal of Number Theory, 73 (1998), 212-227

* Biblioni, L., Paradis, J., Viader, P., ''[http://www.econ.upf.es/eng/research/onepaper.php?id=378 The Derivative of Minkowski's Singular Function]'', Journal of Mathematical Analysis and Applications, (2001) 107-125

* Conley, Randolph M. ''[http://kitkat.wvu.edu:8080/files/3055.1.Conley_Randolph_thesis.pdf A Survey of the Minkowski ?(x) Function]'', Master's Thesis, West Virginia University, (2003)

* Vepstas, Linas, ''[http://www.linas.org/math/chap-minkowski.pdf The Minkowski Question Mark and the Modular Group SL(2,Z)]'', (2004)

* Vepstas, Linas, ''[http://www.linas.org/math/fdist/fdist.html Modular Fractal Measures]'', (2004). ''conjectures that the derivative of the question mark is the limit of a [[modular form]]''.

* Eric W. Weisstein. "[http://mathworld.wolfram.com/MinkowskisQuestionMarkFunction.html Minkowski's Question Mark Function.]" From MathWorld--A Wolfram Web Resource.

[[Category: Fractals]]
[[Category: Number theory]]
[[Category: Special functions]]

Benutzer:Tino Cannst/Minkowski'schen Fragezeichenfunktion

2005-04-18T02:39:52Z

Mathbot: "Removed extra blank lines."

In mathematics, the '''question mark function''' is a function denoted ?(x) whose definition is due to [[Hermann Minkowski]]. If <math>[a_0; a_1, a_2, \cdots]</math> is the [[continued fraction|continued fraction representation]] of an irrational number ''x'', then
:<math>{\rm ?}(x) = a_0 + 2 \sum_{n=1}^\infty (-1)^{n+1}2^{-a_1 - \cdots -a_n}</math>
whereas if <math>[a_0; a_1, a_2, \cdots a_m]</math> is a continued fraction for a rational number, then
:<math>{\rm ?}(x) = a_0 + 2 \sum_{n=1}^m (-1)^{n+1}2^{-a_1 - \cdots -a_n}</math>
It should be noted that if ''a''''m'' is greater than one, then
<math>[a_0; a_1, a_2, \cdots a_m-1, 1]</math> is also a continued fraction for the same number, but the two expressions give identical values for ?(x).

For rational numbers the function may also be defined recursively; if p/q and r/s are reduced fractions such that |ps - rq| = 1 (so that they are adjacent elements of a row of the [[Farey sequence]]) then
:<math>?(\frac{p+r}{q+s}) = \frac12 (?(\frac{p}{q}) + ?(\frac{r}{s}))</math>

Note that in general, any matrix <math>\begin{pmatrix} p & q \\ r & s \end{pmatrix}</math> having unit determinant is by definition a member of the [[modular group]]. The question mark function is self-similar, with the [[modular group]] describing the self-similarity. This follows in part because if <math>p_{n-1}/q_{n-1}</math> and <math>p_{n}/q_{n}</math> are two successive convergents of a [[continued fraction]], then the matrix
<math>\begin{pmatrix} p_{n-1} & p_{n} \\ q_{n-1} & q_{n} \end{pmatrix}</math>
has determinant plus or minus 1.

==Properties of ?(x)==

The question mark function is a strictly increasing and continuous function. It has a derivative almost everywhere, of value zero. At other points either the derivative is not defined at all, or exists in the sense of being infinite--that is, such that (?-1)'(?(x)) equals zero. It sends rational numbers to [[dyadic rational|dyadic rational number]]s, meaning those whose base two representation terminates. It sends quadratic irrationalities to non-dyadic rational numbers. If ?(x) is irrational, then x is either algebraic of degree greater than two, or transcendental. The function is invertible, and the inverse function has also attracted the attention of various mathematicians, in particular [[John Conway]], whose notation for ?-1(x) is x with a box drawn around it. It is an odd function, and satisfies the functional equation ?(x+1) = ?(x)+1; consequently ?(x)-x is an odd periodic function with period one.

The Minkowski question mark function is a special case of fractal curves known as [[de Rham curve]]s.

==References==
* Biblioni, L., Paradis, J., Viader, P., ''A New Light on Minkowski's ?(x) Function'', Journal of Number Theory, 73 (1998), 212-227 http://www.econ.upf.es/eng/research/onepaper.php?id=226

* Biblioni, L., Paradis, J., Viader, P., ''The Derivative of Minkowski's Singular Function'', Journal of Mathematical Analysis and Applications, (2001) 107-125 http://www.econ.upf.es/eng/research/onepaper.php?id=378

* Conley, Randolph M. ''A Survey of the Minkowski ?(x) Function'', Master's Thesis, West Virginia University, 2003 http://kitkat.wvu.edu:8080/files/3055.1.Conley_Randolph_thesis.pdf

* Vepstas, Linas, ''The Minkowski Question Mark and the Modular Group SL(2,Z)'' 2004, http://www.linas.org/math/chap-minkowski/chap-minkowski.html

* Vepstas, Linas, ''Modular Fractal Measures'' 2004, http://www.linas.org/math/fdist/fdist.html ''conjectures that the derivative of the question mark is the limit of a [[modular form]]''.

[[Category: Fractals]]
[[Category: Number theory]]
[[Category: Special functions]]

Burnside-Problem

2005-04-16T20:00:08Z

Mathbot: "Change to the 'MacTutor Biography' template"

One of the oldest open problems in [[group theory]] was first posed by [[William Burnside]] in a paper published in [[1902]]. Some variations of the problem which were also stated in this paper have been resolved; but a full solution to the basic problem is still open [[as of 2004]].

A [[group (mathematics)|group]] ''G'' is called ''periodic'' if every element has finite [[order (group theory)|order]]; in other words, for each ''g'' in ''G'', there exists some positive integer ''n'' such that ''g''''n'' = 1. Clearly, every finite group is periodic. There exist easily defined groups such as the [[p-group | ''p''∞-group]] which are infinite periodic groups; but the latter group cannot be [[generating set of a group | finitely generated]].

The '''general Burnside problem''' can be posed as: if ''G'' is a periodic group, and ''G'' is finitely generated, then is ''G'' necessarily a finite group?

This question was answered in the negative in [[1964]], when Golod and [[Shafarevich]] gave an example of an infinite [[p-group | ''p''-group]] that can be finitely generated.

As a related question which ''seems'' as if it might have an easier answer, consider a periodic group ''G'' with the additional property that there exists a single integer ''n'' such that for all ''g'' in ''G'', ''g''''n'' = 1. A group with this property is said to be ''periodic with bounded exponent'' ''n'', or just a ''group with exponent'' ''n''.

Then the '''Burnside problem''' is stated as, if ''G'' is a finitely generated group with exponent ''n'', is ''G'' finite?

There are exponents ''n'' for which this problem also has a negative answer. [[S.I. Adian]] and [[P.S. Novikov]]
showed in 1968 that for every [[even and odd numbers|odd]] ''n'' with ''n'' > 4381, there are finitely generated exponent ''n'' groups that are infinite. ([[John Britton]] proposed a nearly 300 page alternative proof to the Burside problem in 1973, however Adian ultimately pointed out a flaw in that proof.) A more famous class of counterexamples (given in [[1982]]) are the [[Tarski Monster]]s - finitely generated infinite groups in which every subgroup is [[cyclic group|cyclic]] of order ''p'', where ''p'' is a [[prime number|prime]] greater than 1075.

The problem of completely determining for which particular exponents ''n'' the answer to the Burnside Problem is positive has turned out to be more intractable.

To summarize the results to date, let ''F''''r'' be the [[free group]] of rank ''r''; and given a fixed integer ''n'', let ''F''''r''''n'' be the subgroup of ''F''''r'' generated by the set {''g''''n'' : ''g'' in ''F''''r''}. ''F''''r''''n'' is a [[normal subgroup]] of ''F''''r''; since if ''h'' = ''a''1''n''''a''2''n''...''a''''m''''n'' is in ''F''''r''''n'', then

:''g'' -1''hg'' = (''g'' -1''a''1''n''''g'')(''g'' -1''a''2''n''''g'')...(''g'' -1''a''''m''''n''''g'') = (''g'' -1''a''1''g'')''n''(''g'' -1''a''2''g'')''n''...(''g'' -1''a''''m''''g'')''n''

is also in ''F''''r''''n''.

We then define the ''Burnside free group'' B(''r'', ''n'') to be the [[factor group]] ''F''''r''/(''F''''r''''n'').

If ''G'' is any finitely generated group of exponent ''n'', then ''G'' has a [[presentation of a group | presentation]] including relations {''g''''n'' = 1} for all ''g'' in ''G'', plus some additional relations. ''G'' is then a [[group homomorphism|homomorphic image]] of B(''r'', ''n'') for some ''r''; so the Burnside problem can be re-stated as: for which positive integers ''r'', ''n'' is B(''r'',''n'') finite?

Burnside proved some easy cases in his original paper:

*Clearly if ''r'' = 1, then for all ''n'', B(1, ''n'') = ''C''''n'', the [[cyclic group]] of order ''n''.
*B(''r'', 2) is the direct product of ''r'' copies of ''C''2.
**This follows since, for any ''a'', ''b'' in B(''r'', 2), we have that (''ab'')(''ab'') = 1, and ''a'' = ''a'' -1; therefore ''ab'' = ''ba'', and so B(''r'',2) is abelian, and so every element of B(''r'',2) is of the form ''a''1''n''1''a''2''n''2...''a''''r''''n''''r'', where ''n''''i'' is either 0 or 1 and {''a''''i''} is the set of ''r'' generators.

In addition, Burnside gave finite upper bounds on the order of B(''r'', 3) and B(2,4).

One hundred years later, the following additional results have been established:

*B(''r'',3), B(''r'',4), and B(''r'',6) are finite for all ''r''.
*B(''r'', ''n'') is infinite if ''r'' > 2 and ''n'' > 12.

The particular case of B(''r'', 5) is still an area of intense research. It is not even known whether B(2,5) is finite.

The '''restricted Burnside problem''' (formulated in the [[1930s]]) asks another related question: are there only ''finitely many'' finite ''r''-generator groups of exponent ''n'', [[up to]] [[group isomorphism|isomorphism]]? (An ''r''-generator group is group which can be generated by ''r'' elements.)

If this holds for a given ''r'' and ''n'', then consider subgroups ''H'' and ''K'' of B(''r'', ''n''), where both ''H'' and ''K'' have finite index. The intersection of ''H'' and ''K'' then also has finite index. Let ''M'' be the intersection of ''all'' subgroups of B(''r'', ''n'') which have finite index. ''M'' is a normal subgroup of B(''r'', ''n'') (otherwise, there exists a subgroup ''g'' -1''Mg'' with finite index containing elements not in ''M''). We can then define B0(''r'',''n'') to be the factor group formed by B(''r'',''n'')/''M''. B0(''r'',''n'') is a finite group; and every finite ''r''-generator group of exponent ''n'' is a homomorphic image of B0(''r'',''n'').

The restricted Burnside problem was answered in the affirmative in [[1991]] by [[Efim Zelmanov]], for which he was awarded the [[Fields Medal]] in [[1994]]. The solution relates the problem to deep questions about [[Lie algebra]]s.

==External links==
* [http://www-gap.dcs.st-and.ac.uk/~history/HistTopics/Burnside_problem.html A History of the Burnside Problem];
* {{MacTutor Biography|id=Britton}}
[[Category:Group theory]]