Dissipation factor

2014-01-03T05:14:31Z

46.226.190.2:

In [[geometric group theory]], '''Gromov's theorem on groups of polynomial growth''', named for [[Mikhail Gromov (mathematician)|Mikhail Gromov]], characterizes finitely generated [[Group (mathematics)|groups]] of ''polynomial'' growth, as those groups which have [[nilpotent group|nilpotent]] subgroups of finite [[index of a subgroup|index]].

The [[Growth rate (group theory)|growth rate]] of a group is a [[well-defined]] notion from [[asymptotic analysis]]. To say that a finitely generated group has '''polynomial growth''' means the number of elements of [[length]] (relative to a symmetric generating set) at most ''n'' is bounded above by a [[polynomial]] function ''p''(''n''). The ''order of growth'' is then the least degree of any such polynomial function ''p''.

A ''nilpotent'' group ''G'' is a group with a [[lower central series]] terminating in the identity subgroup.

Gromov's theorem states that a finitely generated group has polynomial growth if and only if it has a nilpotent subgroup that is of finite index.

There is a vast literature on growth rates, leading up to Gromov's theorem. An earlier result of [[Joseph A. Wolf]] showed that if ''G'' is a finitely generated nilpotent group, then the group has polynomial growth. [[Yves Guivarc'h]] and independently [[Hyman Bass]] (with different proofs) computed the exact order of polynomial growth. Let ''G'' be a finitely generated nilpotent group with lower central series

:<math> G = G_1 \supseteq G_2 \supseteq \ldots. </math>

In particular, the quotient group ''G''''k''/''G''''k''+1 is a finitely generated abelian group.

'''The Bass–Guivarc'h formula''' states that the order of polynomial growth of ''G'' is

:<math> d(G) = \sum_{k \geq 1} k \ \operatorname{rank}(G_k/G_{k+1}) </math>

where:
:''rank'' denotes the [[rank of an abelian group]], i.e. the largest number of independent and torsion-free elements of the abelian group.

In particular, Gromov's theorem and the Bass–Guivarch formula imply that the order of polynomial growth of a finitely generated group is always either an integer or infinity (excluding for example, fractional powers).

In order to prove this theorem Gromov introduced a convergence for metric spaces. This convergence, now called the [[Gromov–Hausdorff convergence]], is currently widely used in geometry.

A relatively simple proof of the theorem was found by [[Bruce Kleiner]]. Later, [[Terence Tao]] and [[Yehuda Shalom]] modified Kleiner's proof to make an essentially elementary proof as well as a version of the theorem with explicit bounds.<ref>http://terrytao.wordpress.com/2010/02/18/a-proof-of-gromovs-theorem/</ref><ref>{{cite arxiv |eprint=0910.4148 |author1=Yehuda Shalom |author2=Terence Tao |title=A finitary version of Gromov's polynomial growth theorem |class=math.GR |year=2009}}</ref>

== References ==
<references/>
* H. Bass, The degree of polynomial growth of finitely generated nilpotent groups, ''Proceedings London Mathematical Society'', vol 25(4), 1972
* M. Gromov, Groups of Polynomial growth and Expanding Maps, [http://www.numdam.org/numdam-bin/feuilleter?id=PMIHES_1981__53_ ''Publications mathematiques I.H.É.S.'', 53, 1981]
* Y. Guivarc'h, Groupes de Lie à croissance polynomiale, C. R. Acad. Sci. Paris Sér. A–B 272 (1971). [http://www.numdam.org/item?id=BSMF_1973__101__333_0]
* {{Cite arxiv | last1=Kleiner | first1=Bruce | year=2007 | title=A new proof of Gromov's theorem on groups of polynomial growth | arxiv=0710.4593}}
* J. A. Wolf, Growth of finitely generated solvable groups and curvature of Riemannian manifolds, ''Journal of Differential Geometry'', vol 2, 1968

[[Category:Theorems in group theory]]
[[Category:Nilpotent groups]]
[[Category:Infinite group theory]]
[[Category:Metric geometry]]
[[Category:Geometric group theory]]

Continuously variable slope delta modulation

2013-12-26T00:53:07Z

46.226.190.2:

In [[recreational mathematics]], a '''Harshad number''' (or '''Niven number''') in a given [[number base]], is an [[integer]] that is divisible by the [[digit sum|sum of its digits]] when written in that base.
Harshad numbers in base ''n'' are also known as '''''n''-Harshad''' (or '''''n''-Niven''') numbers.
Harshad numbers were defined by [[D. R. Kaprekar]], a [[mathematician]] from [[India]]. The word "Harshad" comes from the [[Sanskrit]] ''{{IAST|harṣa}}'' (joy) + ''{{IAST|da}}'' (give), meaning joy-giver. The term “Niven number” arose from a paper delivered by [[Ivan M. Niven]] at a conference on [[number theory]] in 1977. All integers between [[0 (number)|zero]] and ''n'' are ''n''-Harshad numbers.
To date there appear to be no applications for Harshad numbers, not even within pure mathematics.

Stated mathematically, let ''X'' be a positive integer with ''m'' digits when written in base ''n'', and let the digits be ''ai'' (''i'' = 0, 1, ..., ''m'' − 1). (It follows that ''ai'' must be either zero or a positive integer up to ''n'' − 1.) ''X'' can be expressed as

:<math>X=\sum_{i=0}^{m-1} a_i n^i.</math>

If there exists an integer ''A'' such that the following holds, then ''X'' is a Harshad number in base ''n'':

:<math>X=A\sum_{i=0}^{m-1} a_i.</math>

Harshad numbers in [[base 10]] form the sequence:

: [[1 (number)|1]], [[2 (number)|2]], [[3 (number)|3]], [[4 (number)|4]], [[5 (number)|5]], [[6 (number)|6]], [[7 (number)|7]], [[8 (number)|8]], [[9 (number)|9]], [[10 (number)|10]], [[12 (number)|12]], [[18 (number)|18]], [[20 (number)|20]], [[21 (number)|21]], [[24 (number)|24]], [[27 (number)|27]], [[30 (number)|30]], [[36 (number)|36]], [[40 (number)|40]], [[42 (number)|42]], [[45 (number)|45]], [[48 (number)|48]], [[50 (number)|50]], [[54 (number)|54]], [[60 (number)|60]], [[63 (number)|63]], [[70 (number)|70]], [[72 (number)|72]], [[80 (number)|80]], [[81 (number)|81]], [[84 (number)|84]], [[90 (number)|90]], [[100 (number)|100]], [[102 (number)|102]], [[108 (number)|108]], [[110 (number)|110]], [[111 (number)|111]], [[112 (number)|112]], [[114 (number)|114]], [[117 (number)|117]], [[120 (number)|120]], [[126 (number)|126]], [[132 (number)|132]], [[133 (number)|133]], [[135 (number)|135]], [[140 (number)|140]], [[144 (number)|144]], [[150 (number)|150]], [[152 (number)|152]], [[153 (number)|153]], [[156 (number)|156]], [[162 (number)|162]], [[171 (number)|171]], [[180 (number)|180]], [[190 (number)|190]], [[192 (number)|192]], [[195 (number)|195]], [[198 (number)|198]], [[200 (number)|200]], [[201 (number)|201]], ... {{OEIS|id=A005349}}

A number which is a Harshad number in any number base is called an '''all-Harshad number''', or an '''all-Niven number'''. There are only four all-Harshad numbers: [[1 (number)|1]], [[2 (number)|2]], [[4 (number)|4]], and [[6 (number)|6]].

== What numbers can be Harshad numbers? ==

Given the [[divisibility test]] for [[9 (number)|9]], one might be tempted to generalize that all numbers divisible by 9 are also Harshad numbers. But for the purpose of determining the Harshadness of ''n'', the digits of ''n'' can only be added up once and ''n'' must be divisible by that sum; otherwise, it is not a Harshad number. For example, [[99 (number)|99]] is not a Harshad number, since 9 + 9 = 18, and 99 is not divisible by 18.

The base number (and furthermore, its powers) will always be a Harshad number in its own base, since it will be represented as "10" and 1 + 0 = 1.

For a [[prime number]] to also be a Harshad number it must be less than or equal to the base number. Otherwise, the digits of the prime will add up to a number that is more than 1 but less than the prime and, obviously, it will not be divisible. For example: 11 is not Harshad in base 10 because the sum of its digits "11" is 1+1=2 and 11 is not divisible by 2, while in [[hexadecimal]] the number 11 may be represented as "B", the sum of whose digits is also B and clearly B is divisible by B, ergo it is Harshad in base 16.

Although the sequence of [[factorial]]s starts with Harshad numbers in base 10, not all factorials are Harshad numbers. 432! is the first that is not.

== Consecutive Harshad numbers ==

=== Maximal runs of consecutive Harshad numbers ===
Cooper and Kennedy proved in 1993 that no 21 consecutive integers are all Harshad numbers in base 10.<ref>{{citation | zbl=0776.11003 | last1=Cooper | first1=Curtis | last2=Kennedy | first2=Robert E. | title=On consecutive Niven numbers | journal=[[Fibonacci Quarterly]] | volume=31 | number=2 | pages=146–151 | year=1993 | issn=0015-0517 |url=http://www.fq.math.ca/Scanned/31-2/cooper.pdf}}</ref><ref name=HBII382>{{cite book | last1=Sándor | first1=Jozsef | last2=Crstici | first2=Borislav | title=Handbook of number theory II | location=Dordrecht | publisher=Kluwer Academic | year=2004 | isbn=1-4020-2546-7 | zbl=1079.11001|page=382}}</ref> They also constructed infinitely many 20-tuples of consecutive integers that are all 10-Harshad numbers, the smallest of which exceeds 1044363342786.

{{harvs|authorlink=Helen G. Grundman|first=H. G.|last=Grundman|year=1994|txt}} extended the Cooper and Kennedy result to show that there are 2''b'' but not 2''b''+1 consecutive ''b''-Harshad numbers.<ref name=HBII382/><ref>{{citation | last = Grundman | first = H. G. | authorlink=Helen G. Grundman | title = Sequences of consecutive ''n''-Niven numbers | journal = [[Fibonacci Quarterly]] | volume = 32 | issue = 2 | year=1994 | pages = 174–175 | zbl=0796.11002 | issn=0015-0517 |url=http://www.fq.math.ca/Scanned/32-2/grundman.pdf}}</ref>
This result was strengthened to show that there are infinitely many runs of 2''b'' consecutive ''b''-Harshad numbers for ''b'' = 2 or 3 by {{harvs|authorlink=T. Tony Cai|first=T.|last=Cai|year=1996|txt}}<ref name=HBII382/> and for arbitrary ''b'' by [[Brad Wilson (mathematician)|Brad Wilson]] in 1997.<ref>{{citation | last1=Wilson | first1=Brad | title=Construction of 2''n'' consecutive ''n''-Niven numbers | journal=[[Fibonacci Quarterly]] | volume=35 | pages=122–128 | year=1997 | issn=0015-0517 |url=http://www.fq.math.ca/Scanned/35-2/wilson.pdf}}</ref>

In [[binary numeral system|binary]], there are thus infinitely many runs of four consecutive Harshad numbers and in [[ternary numeral system|ternary]] infinitely many runs of six.

In general, such maximal sequences run from ''N · bk - b'' to ''N · bk'' + (''b''-1) , where ''b'' is the base, ''k'' is a relatively large power, and ''N'' is a constant.
Given one such suitably chosen sequence we can convert it to a larger one as follows:
* Inserting zeroes into ''N'' will not change the sequence of digital sums (just as 21, 201 and 2001 are all 10-Harshad numbers).
* If we insert ''n'' zeroes after the first digit, α (worth α''bi''), we increase the value of ''N'' by α''bi(bn - 1)'' .
* If we can ensure that ''bn - 1'' is divisible by all digit sums in the sequence, then the divisibility by those sums is maintained.
* If our initial sequence is chosen so that the digit sums are [[coprime]] to ''b'', we can solve ''bn = 1'' modulo all those sums.
* If that is not so, but the part of each digit sum not coprime to ''b'' divides α''bi'', then divisibility is still maintained.
* ''(Unproven)'' The initial sequence is so chosen.
Thus  our initial sequence yields an infinite set of solutions.

=== First runs of exactly ''n'' consecutive 10-Harshad numbers ===
The smallest naturals starting runs of exactly ''n'' consecutive 10-Harshad numbers (i.e., smallest ''x'' such that ''x'', ''x''+1, ..., ''x''+''n''-1 are Harshad numbers but ''x''-1 and ''x''+''n'' are not) are as follows {{OEIS|id=A060159}}:
{| class="wikitable"
|-
! ''n'': !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10
|-
| ''x'': || 12 || 20 || 110 || 510 || 131052 || 12751220 || 10000095 || 2162049150 || 124324220 || 1
|-
| '''''n''''': || '''11''' || '''12''' || '''13''' || '''14''' || '''15''' || '''16''' || '''17''' || '''18''' || '''19''' || '''20'''
|-
| ''x'': || 920067411130599 || 43494229746440272890 || 121003242000074550107423034⋅1020 - 10 || 420142032871116091607294⋅1040 - 04 || ? || 50757686696033684694106416498959861492⋅10280 - 9 || 14107593985876801556467795907102490773681⋅10280 - 10 || ? || ? || ?
|}
By the previous section, no such ''x'' exists for ''n'' > 20.

== Estimating the density of Harshad numbers ==

If we let ''N''(''x'') denote the number of Harshad numbers ≤ x, then for any given ε > 0,

:<math>x^{1-\varepsilon} \ll N(x) \ll \frac{x\log\log x}{\log x}</math>

as shown by [[Jean-Marie De Koninck]] and Nicolas Doyon;<ref>{{citation|first1=Jean-Marie|last1=De Koninck|first2=Nicolas|last2=Doyon|title=On the number of Niven numbers up to ''x''|journal=[[Fibonacci Quarterly]]|volume=41|issue=5|date=November 2003|pages=431–440}}.</ref> furthermore, De Koninck, Doyon and Kátai<ref>{{citation|first1=Jean-Marie|last1=De Koninck|first2=Nicolas|last2=Doyon|first3=I.|last3=Katái|title=On the counting function for the Niven numbers|journal=[[Acta Arithmetica]]|volume=106|year=2003|pages=265–275}}.</ref> proved that

:<math>N(x)=(c+o(1))\frac{x}{\log x}</math>

where ''c'' = (14/27) log 10 ≈ 1.1939.

== Nivenmorphic numbers ==

A '''Nivenmorphic number''' or '''Harshadmorphic number''' for a given number base is an integer ''t'' such that there exists some Harshad number ''N'' whose [[digit sum]] is ''t'', and ''t'', written in that base, terminates ''N'' written in the same base.

For example, 18 is a Nivenmorphic number for base 10:

16218 is a Harshad number
16218 has 18 as digit sum
18 terminates 16218

Sandro Boscaro determined that for base 10 all positive integers are Nivenmorphic numbers except [[11 (number)|11]].<ref>{{citation|first=Sandro|last=Boscaro|title=Nivenmorphic integers|journal=[[Journal of Recreational Mathematics]]|volume=28|issue=3|year=1996–1997|pages=201–205}}.</ref>

== Multiple Harshad numbers ==
{{harvtxt|Bloem|2005}} defines a ''multiple Harshad number'' as a Harshad number that, when divided by the sum of its digits, produces another Harshad number.<ref>{{citation|first=E.|last=Bloem|year=2005|title=Harshad numbers|journal=[[Journal of Recreational Mathematics]]|volume=34|issue=2|page=128}}.</ref> He states that 6804 is "MHN-3" on the grounds that

:<math>
\begin{array}{l}
6804/18=378\\
378/18=21\\
21/3=7
\end{array}
</math>

and went on to show that 2016502858579884466176 is MHN-12. The number 10080000000000 = 1008·1010, which is smaller, is also MHN-12. In general, 1008·10''n'' is MHN-(''n''+2).

== References ==
{{reflist}}

== External links ==
* [http://www.harshad-numbers.com/en/ Harshad Numbers]
* [http://www.numbers-of-harshad.com/ Numbers of Harshad]

{{Classes of natural numbers}}
[[Category:Base-dependent integer sequences]]

formulasearchengine - User contributions [en]

Dissipation factor

Continuously variable slope delta modulation