Wednesday, December 9, 2009

December 9 - Nikolai Luzin

Nikolai Nikolaevich Luzin Born on December 9, 1883 (Irkutsk, Russia), he is recognized among the founders of descriptive set theory. His Ph.D. is from Moscow State University (1915, "The Integral and Trigonometric Series", advisor Dimitri Egorov). The encounter with Pavel Florensky and his religious thought played an important role in helping Luzin overcome the personal crisis he went through in his early 20's. Later on, he led the research group known as Luzitania, together with Egorov. Some references: Math Genealogy Project, Mac Tutor biography. He suffered persecution, being considered an "enemy under the mask of a Soviet citizen". He died on January 28, 1950.

Tuesday, December 8, 2009

Hindu-Arabic numerals in Europe

Here is a passage from "Liber Abaci" (1202) featuring the Hindu-Arabic numerals:

"Novem figure indorum he sunt 9 8 7 6 5 4 3 2 1 Cum his itaque novem figuris, et cum hoc signo 0, quod arabice zephirum appellatur, scribitur quilibet numerus, ut inferius demonstratur." Leonardo Pisano (Fibonacci) - Liber Abaci

However, it appears that the European debut of the Hindu-Arabic numerals is in an illuminated manuscript dated 976 ("Codex Vigilanus") - though without the zero:







Obviously, their use becomes widespread after the invention of printing.

Monday, November 23, 2009

Fibonacci numbers and the extreme and mean ratio - some history

Ruth Tatlow's article The Use and Abuse of Fibonacci Numbers and the Golden Section in Musicology Today (Understanding Bach, 1, 69-85, 2006) besides being very interesting in itself as a documented criticism of the "Golden numberism [that] has thoroughly infected musicology", incidentally provides useful references for those interested in the history of the representation of the EMR ("extreme and mean ratio" or "golden section") as the limit of the sequence of quotients Fn+1/Fn of consecutive Fibonacci numbers [1]. One may wonder who noticed this first? Leonardo Pisano (c. 1170 – c. 1250, also known as Fibonacci)? Not even close!

Evidence that this fact was noticed as early as the beginning of the 16th century was discovered by Leonard Curchin and Roger Herz-Fischler (handwritten annotation in the 1509 Luca Pacioli's edition of Elements [2]). When it comes to published work which associates the EMR with the limit of the sequence of quotients of consecutive Fibonacci numbers, Johannes Kepler wrote [3] the following, in 1611, about "this proportion that the geometers of today call divine":

It is impossible to provide a perfect example in round numbers. However, the further we advance from the number one, the more perfect the example becomes. Let the smallest numbers be 1 and 1... Add them, and the sum will be 2; add to this the greater of the 1s, result 3; add 2 to this, and get 5; add 3, get 8; 5 to 8, 13; 8 to 13, 21. As 5 is to 8, so 8 is to 13 approximately, and as 8 to 13, so 13 is to 21, approximately.
However, as communicated in 1995 by Peter Schreiber [4], in a rare book by the German reckoning master Simon Jacob (d. 1564) one can find a remark that the sequence of quotients of consecutive Fibonacci numbers approaches the EMR.

NOTES

[1] The term "extreme and mean ratio" goes back to Euclid's "Elements". Luca Pacioli introduced the "divine proportion" term in 1509, while the term "golden section" was introduced in 1835 by Martin Ohm. The exact value for the EMR is (1+sqrt(5))/2. The phrase "Fibonacci sequence" was coined by Edouard Lucas (1842-1891).
[2] Leonard Curchin and Roger Herz-Fischler, "De quand date le premier rapprochement entre la suite de Fibonacci et la division en extrême et moyenne raison?" (French) ["When were the first parallels drawn between the Fibonacci sequence and the golden section?"], Centaurus 28 (1985), no. 2, 129-138.
[3] Kepler, Johannes. Vom sechseckigen Schnee. (German) [On hexagonal snowflakes]. Translated from the Latin and with an introduction and notes by Dorothea Goetz. Ostwald's Classics of the Exact Sciences, 273. Akademische Verlagsgesellschaft Geest & Portig K.-G., Leipzig, 1987.
[4] Peter Schreiber, "A Supplement to J. Shallit’s Paper "Origins of the analysis of the Euclidean algorithm"", Historia Mathematica, Vol. 22, Issue 4, 422-424 (1995). http://poncelet.math.nthu.edu.tw/disk5/js/history/1033a.pdf

Sunday, November 22, 2009

Arthur Stanley Eddington (1882-1944)

  • Arthur Stanley Eddington - Mac Tutor Biography
  • Sir Arthur Stanley Eddington, OM, FRS (28 December 1882 – 22 November 1944) believed he had identified an algebraic basis for fundamental physics, which he termed "E-frames" (representing a certain group - a Clifford algebra). While his theory has long been neglected by the general physics community, similar algebraic notions underlie many modern attempts at a grand unified theory. Moreover, Eddington's emphasis on the values of the fundamental constants, and specifically upon dimensionless numbers derived from them, is nowadays a central concern of physics.
  • One recent tribute to Eddington's ideas: an article on "The Numbers Universe" (Ross A. McPherson, EJTP 5, No. 18, 81–94 (2008)).

Tuesday, October 20, 2009

The Axiom of Choice

Three useful links dealing with the Axiom of Choice: The Axiom of Choice - Stanford Encyclopedia of Philosophy entry by John L. Bell, the University of Western Ontario; The Axiom of Choice (a short paper by Prof. John L. Bell) ; The Relative Consistency of the Axiom of Choice - Mechanized Using Isabelle/ZF by Lawrence C. Paulson, Computer Laboratory Univ. of Cambridge. An important result, in a categorical setting linked to intutionistic set theory, was obtained by Radu Diaconescu (Axiom of choice and complementation, Proc. Amer. Math. Soc. 51, 1975, 176-178): a topos satisfying the axiom of choice must be boolean (in short... the axiom of choice implies the law of the excluded middle).

Tuesday, October 13, 2009

A conjecture on primes

The Feit-Thompson conjecture: there are no distinct prime numbers p and q for which (p^q-1)/(p-1) divides (q^p-1)/(q-1). Note that a stronger statement stating that (p^q-1)/(p-1) and (q^p-1)/(q-1) are relatively prime whenever p and q are distinct primes does not hold.
Indeed, 112643 = GCD((3313^17 -1)/3312, (17^3313-1)/16) - see Stevens (1971).
Note that (3313^17 - 1)/3312 factors as
78115430278873040084455537747447422887 * 23946003637421 * 112643,
while (17^3313-1)/16 modulo (3313^17 -1)/3312 equals...
149073454345008273252753518779212742886488244343395482423
The 1970 Fields medalist and 2008 Abel prize winner John Griggs Thompson was born on Ottawa, KS on October 13.

Sunday, October 4, 2009

Dimitrie Pompeiu (1873–1954)

Dimitrie Pompeiu (October 4, 1873, Broscǎuţi, Botoşani – October 8, 1954, Bucharest) - orthodox christian, and one of the greatest Romanian mathematicians. He is remembered in the mathematical world for numerous contributions such as: the set distance [1] that he introduced in his 1905 Université de Paris dissertation published in the same year in the Annales de la faculté des sciences de Toulouse (a set distance was introduced in a slightly different form in 1914 by Hausdorff, who credited Pompeiu's definition though), his contributions in complex analysis, including the areolar derivative [2] and the seminal Cauchy-Pompeiu's formula (higher dimensional analogues of the Cauchy-Pompeiu formula are topics of current research, while the formula was used in the theory of functions of several complex variables by Dolbeault and Grothendieck [5]), and for the celebrated Pompeiu's Conjecture that he formulated in his 1929 C. R. Acad. Sci. Paris article [4], a conjecture not fuly proved yet. Still, elegant analogues of Pompeiu's Conjecture continue to be proved in other areas [6] - this is an indicator of the fertility of the idea.

REFERENCES

[1] T. Bârsan and D. Tiba. One hundred years since the introduction of the set distance by Dimitrie Pompeiu. Institute of Mathematics of the Romanian Academy.
[2] D. Pompeiu. Sur une classe de fonctions d'une variable complexe. Rendiconti del Circolo Matematico di Palermo, t. XXXIII, Ist sem. 1912, pp. 108-113.
[3] Pompeiu's biography from the The MacTutor History of Mathematics archive.
[4] D. Pompeiu. Sur certains systèmes d'équations linéaires et sur une propriété intégrale des fonctions de plusieurs variables, Comptes Rendus de l'Académie des Sciences Paris Série I. Mathématique, 188, 1138 –1139 (1929).
[5] R. Remmert. Theory of Complex Functions. Graduate Texts in Mathematics, Springer Verlag, 2nd Edition (1989).
[6] D. Zeilberger. Pompeiu's problem on Discrete Space. Proc. Natl. Acad. Sci. USA, Vol. 75 (8), 3555-3556 (1978).

Monday, September 28, 2009

2009 Miami University Fall Conference

"The Teaching of Undergraduate Mathematics"
September 25-26, 2009
Miami University Fall Conference, Oxford, OH.
Difference Quotient Revisited (a Classroom Supplement)
Fall Conference 2009 - Miami University

Friday, September 18, 2009

Bernhard Riemann

Georg Friedrich Bernhard Riemann (September 17, 1826 – July 20, 1866) - one of the greatest mathematicians of all time.
Dedekind has a deeply touching account of Riemann's final moments, his passing away being marked by the words of Lord's prayer. Riemann's tombstone (see here and here) in Biganzolo (Italy) refers to Romans 8:28 ("And we know that all things work together for good to them that love God, to them who are the called according to his purpose"):
Here rests in God
Georg Friedrich Bernhard Riemann
Professor in Göttingen
born in Breselenz, September 17th, 1826
died in Selasca, Juli 20th, 1866
---
Those, who love God, all things
must serve to its best manner.

Friday, August 21, 2009

Gödel's incompleteness between use and abuse

  • A number of misinterpretations involving Gödel's incompleteness theorems are addressed in the article The Popular Impact of Gödel’s Incompleteness Theorem (Notices of the AMS, April 2006, p. 440) by the late Torkel Franzén (he passed away in 2006 due to cancer, at age 56), author of "Gödel's Theorem: An Incomplete Guide to its Use and Abuse" (Wellesley, MA: AK Peters, Ltd., 2005).
  • In the final part of his article "The nature and significance of Gödel’s incompleteness theorems" (Institute for Advanced Study, Princeton, Gödel Centenary Program, 2006), Solomon Feferman (from Stanford University, one of the world's leading logicians) questions the relevance of Gödel’s incompleteness in relation to the fundamental laws of physics and especially the "theories of everything" matters.

Tuesday, August 11, 2009

An application of elliptic curves to one-time pad cryptography

Award-winning poster presentation at the 2007 AMS/MAA Joint Mathematical Meetings held in New Orleans, LA.

Sunday, August 2, 2009

GPF sequences

On a class of recurrent sequences based on the greatest prime factor function. Award-winning poster presentation at the 2007 AMS/MAA Joint Mathematical Meetings held in New Orleans, LA.

Tuesday, July 28, 2009

A neat "Theorem of the Day"!

I would like to post this, because it's a really neat result and also it is today's (July 28th) "Theorem of the Day"!

"The Fifteen Theorem", announced in 1993 by Conway and Schneeberger, states that if a positive-definite quadratic form having integer matrix represents every positive integer up to 15 then it represents every positive integer. In its strongest form, if a positive-definite quadratic form having integer matrix represents 1, 2, 3, 5, 6, 7, 10, 14, and 15, then it represents every positive integer. See Manjul Bhargava's article "The Fifteen Theorem, and Generalizations".

Hilbert 10th - supplement

Hilbert's Tenth Problem: a History of Mathematical Discovery (Diophantus, Fermat, Hilbert, Julia Robinson, Nikolay Vorob'ev, Yuri Matiyasevich)

Tuesday, July 21, 2009

Thursday, July 16, 2009

Saturday, June 27, 2009

Notes on the nine-point circle, the Simson line and related topics

Mihai Caragiu - NOTES ON THE NINE POINT CIRCLE, THE SIMSON LINE AND RELATED TOPICS (Mathematics Bonus Files - April 17, 2009). ABSTRACT: These notes are based on the proofs of the nine point circle and the Simson line theorems prepared by the author for the 2006 and 2007 Summer Honors Institute camps held at the Ohio Northern University, and on the author’s 2007 October 26 talk presented at the Ohio MAA Fall Meeting held at Wittenberg University.

Tuesday, June 16, 2009

Monday, June 8, 2009

Giovanni Domenico Cassini (1625–1712)




















Giovanni Domenico Cassini
was born on June 8, 1625. He investigated the curves that are now known as the Cassini ovals defined by equations of the form




where q1 and q2 are fixed points, "dist" is the Euclidean distance in the plane, and b is a constant. The above picture displays a few Cassini ovals, with foci q1(-1, 0) and q2(1, 0), annotated with the value of b2.

In 1680, while director of the Paris Observatory he discovered the identity




satisfied by the Fibonacci numbers. This is now known as the Cassini identity. A quick proof by using determinants:





A bijective proof was provided by M. Werman and D. Zeilberger - "A bijective proof of Cassini's Fibonacci identity", Discrete Mathematics 58 (1), 109 (1986).

Also see the Cassini biography from MacTutor.

Sunday, May 31, 2009

Greatest prime factor sequences


The greatest prime factor function (gpf) can be used to generate a class of prime sequences as follows: x(1) = p (an arbitrary prime) and x(n+1) = gpf (a*x(n) + b) for n ≥ 1 (a, b are fixed positive integers). Computer evidence suggests that all "linear gpf sequences" are ultimately periodic, regardless the values chosen for a and b. For example, the sequences corresponding to a = 2, b = 1 and p arbitrary appear to enter the period 3, 7, 5, 11, 23, 47, 19, 13. For a = 6, b = 5, x(1) = 2, the period is pretty long: 23, 13, 83, 503, 3023, 18143, 108863, 9749, 137, 827, 4967, 727, 397, 31, 191, 1151, 6911, 367, 2207, 1019, 211, 41, 251, 1511, 193, 1163, 69. Multiple limit cycles are possible - for example in the case a = 16 and b = 1, the choice x(1)=2 leads to the period 37, 593, 3163, 229, 733, 317, 89, 19, 61, 977, 193, 3089, 659, while the choice x(1) = 47 leads to the period 251, 103, 97, 1553. So far we proved the "gpf conjecture" in the special case in which a is a divisor of b.
REFERENCES:
1. Caragiu, M. and Scheckelhoff, L. The Greatest Prime Factor and Related Sequences., JP J. of Algebra, Number Theory and Appl. 6, 403-409 (2006).
2. Mihai Caragiu. Recurrent sequences based on the greatest prime factor function. In Abstracts of the Papers Presented to the American Mathematical Society, Meeting #1020, University of Cincinnati, 1020-11-247 (2006).

Monday, May 4, 2009

Balancing the frequencies

Some might find useful to assign +1 or –1 weights to the letters in the English alphabet so that the weighted sum of the frequencies of the letters in the "generic" plain English text is, in absolute value, as small as possible. A possible weight assignment is given in the list below. The number listed at the beginning of every row is 100,000 times the proportion of the corresponding letter (based on the letter frequencies list displayed in Wikipedia, in reference to the "Relative Frequencies of Letters in General English Plain text", from Cryptographical Mathematics, by Robert Edward Lewand). In this weight assignment, the weighted sum is not zero - indeed it is 1 (this is because the original list of frequencies is not perfectly normalized - they add up to 99.999%) and thus optimal, since the sum of the numbers initializing the rows below is odd (which rules out a partition in two subsets with equal sums) . This corresponds to a frequency "defect" of 0.001%. This simple example may be seen in relation to the general "subset sum problem". We can use this "weight assignment" to generate +1/–1 "random walks" out of string characters.

12702(e)–1
9056(t)–1
8167(a)+1
7507(o)–1
6966(i)+1
6749(n)+1
6327(s)–1
6094(h)–1
5987(r)+1
4253(d)+1
4025(l)+1
2782(c)–1
2758(u)+1
2406(m)+1
2360(w)+1
2228(f)+1
2015(g)–1
1974(y)+1
1929(p)–1
1492(b)–1
978(v)+1
772(k)+1
153(j)+1
150(x)+1
95(q)–1
74(z)+1

Wednesday, April 15, 2009

Rotations and translations revisited

Bowling Green, April 3 - "Rotations and translations revisited" (contributed talk, 2009 Ohio MAA Spring Meeting). ABSTRACT: "By using a series of elementary plane geometry problems, we will illustrate the general result stating that the composition of a number of plane rotations of angles adding up to an integer multiple of 2*pi is a plane translation. We will discuss the case of collinear rotation centers, the case in which the rotation centers form a regular polygon, a general connection with discrete Fourier transforms, and also a limit case in which the number of rotation centers goes to infinity."





Seven Bridges of Königsberg...

Monday, April 6, 2009

An irrational logarithm

A short problem proposed by myself for a recent student team competition, held in Bowling Green:

Show that the logarithm in base 4+sqrt(5) of 6+sqrt(5) is irrational.
The proof proceeds by contradiction. Assume the logarithm in base 4+sqrt(5) of 6+sqrt(5) equals p/q with p,q positive integers. Then

(4+sqrt(5))^p=(6+sqrt(5))^q (*)
By taking conjugates,

(4-sqrt(5))^p=(6-sqrt(5))^q (**)
Multiplying (*) and (**) term by term we get

11^p=31^q.
The fundamental theorem of arithmetic tells us this cannot happen.

Saturday, March 14, 2009

Sierpinski numbers

A Sierpinski number is an odd positive integer k such that all integers of the form k2n + 1 (with n taking positive integer values) are composite. In [1], Sierpinski showed that there are infinitely many k with this property. The "Sierpinski problem" asks:
" What is the smallest Sierpinski number ? "
It is conjectured that the answer is k = 78557 (the fact that 78557 is a Sierpinski number was discovered in 1962 by John Selfridge).

Waclaw Sierpinski was born on March 14, 1882 in Warsaw.
[1] Sierpiński, Waclaw "Sur un problème concernant les nombres k2n + 1." Elemente der Mathematik 15, 73-74 (1960).

Friday, March 6, 2009

Ferdinand von Lindemann (1852 - 1939)

Carl Louis Ferdinand von Lindemann died 70 years ago. In 1882 he provided the first proof of the transcendence of Pi - in other words, Pi is not a root of any non-zero polynomial with rational coefficients. As a corollary, this provided a negative answer to the "squaring the circle" problem (one of the oldest geometry problems, asking whether it's possible to construct a square with the same area as a given circle by using only a finite number of steps involving compass and straightedge).

For an informal and very brief introduction to the term "transcendental number" we can start by first defining an algebraic number to be a number - real or complex - that is a root of some non-zero polynomial with rational coefficients. For example,





is algebraic, since it is (you check!) a root of the equation





One could say that there are "very few" algebraic numbers - technically they form a countable "measure-zero subset" of the real number line (or of the complex plane, if we speak about complex algebraic numbers). The transcendental numbers (whether real or complex) are precisely the numbers that are not algebraic. Here we can say just the opposite: "almost all" numbers are transcendental. Intuitively, if we imagine a point-like "shuttle" landing at random on some interval "planet" [a,b] with b > a , then the probability of the landing site being transcendental is 1. The tricky part is that even if "almost all" numbers are transcendental, it may be very hard to prove that a given number is transcendental! The study of transcendental numbers involves very sophisticated, elegant mathematics.

Monday, February 23, 2009

Nikolai Ivanovich Lobachevsky reporting on 1826, February 23...

1826, February 23 (that's February 11 in "old-style") - Nikolai Ivanovich Lobachevsky reported on a geometry in which the fifth postulate was not true to the session of the department of physics and mathematics at the University of Kazan.

From wikipedia, under Nikolai Lobachevsky's work:
Lobachevsky's main achievement is the development (independently from János Bolyai) of a non-Euclidean geometry, also referred to as Lobachevskian geometry. Before him, mathematicians were trying to deduce Euclid's fifth postulate from other axioms. Euclid's fifth is a rule in Euclidean geometry which states (in John Playfair's reformulation) that for any given line and point not on the line, there is one parallel line through the point not intersecting the line. Lobachevsky would instead develop a geometry in which the fifth postulate was not true. This idea was first reported on February 23 (Feb. 11, O.S.), 1826 to the session of the department of physics and mathematics, and this research was printed in the UMA (Вестник Казанского университета) in 1829–1830. Lobachevsky wrote a paper about it called A concise outline of the foundations of geometry that was published by the Kazan Messenger but was rejected when the St. Petersburg Academy of Sciences submitted it for publication.

The non-Euclidean geometry that Lobachevsky developed is referred to as hyperbolic geometry. Lobachevsky replaced Euclid's parallel postulate with the one stating that there is more than one line that can be extended through any given point parallel to another line of which that point is not part; a famous consequence is that the sum of angles in a triangle must be less than 180 degrees. Non-Euclidean geometry is now in common use in many areas of Mathematics and Physics, such as general relativity; and hyperbolic geometry is now often referred to as "Lobachevskian geometry" or "Bolyai-Lobachevskian geometry".

Some mathematicians and historians, have wrongfully claimed that Lobachevsky stole his concept of non-Euclidean geometry from Gauss, which is untrue - Gauss himself appreciated Lobachevsky's published works very highly, but they never had personal correspondence between them prior to the publication. In fact out of the three people that can be credited with discovery of hyperbolic geometry - Gauss, Lobachevsky and Bolyai, Lobachevsky rightfully deserves having his name attached to it, since Gauss never published his ideas and out of the latter two Lobachevsky was the first who duly presented his views to the world mathematical community.

Lobachevsky's magnum opus Geometriya was completed in 1823, but was not published in its exact original form until 1909, long after he had died. Lobachevsky was also the author of New Foundations of Geometry (1835-1838). He also wrote Geometrical Investigations on the Theory of Parallels (1840) and Pangeometry (1855).

Another of Lobachevsky's achievements was developing a method for the approximation of the roots of algebraic equations. This method is now known as Dandelin-Gräffe method, named after two other mathematicians who discovered it independently. In Russia, it is called the Lobachevsky method. Lobachevsky gave the definition of a function as a correspondence between two sets of real numbers (Dirichlet gave the same definition independently soon after Lobachevsky).

Carl Friedrich Gauss (30 April 1777 – 23 February 1855)

Johann Carl Friedrich Gauss - "Princeps mathematicorum", died in Göttingen on February 23, 1855.

Friday, February 20, 2009

Fibonacci modulo m

The general problem of the periods of the Fibonacci sequence modulo m is definitely non-trivial (with the case m = p - prime - playing a very important role). A quick reference can be found here (The Fibonacci Sequence Modulo M). Also see the article (in pdf) on "The Fibonacci sequence modulo p^2...".

An example that teachers use relatively often as a middle-school problem: "Find the period of the sequence of the last digits of the Fibonacci numbers"! That will correspond to the modulus m=10, the answer is 60, and the elements of the period are
0,1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,
9,9,8,7,5,2,7,9,6,5,1,6,7,3,0,3,3,6,9,5,4,9,3,2 ,5,7,2,9,1
In the previous blog entry, the modulus m is 2011 (that is the 305-th prime) and the period of the Fibonacci sequence modulo m is 2010.

Wednesday, February 18, 2009

Distribution of the quadratic residues and nonresidues of the Fibonacci numbers modulo a prime p


I was just curious to visualize a plot of the cumulative sum of the sequence of quadratic symbols of the Fibonacci numbers modulo p (p - prime) within a period of that sequence. Here it is, for p=2011. These graphs stimulate the students' interest in deeper mathematical topics. They may be seen as useful educational tools.

Wednesday, February 4, 2009

Octacube

OCTACUBE: a sculpture designed by Dr. Adrian Ocneanu, Professor of Mathematics at Penn State and built by the machinists in the Penn State Engineering Shop. Jill Grashof Anderson (PSU '65, Mathematics) sponsored the sculpture, dedicated to the memory of her husband, Kermit Anderson (PSU '65 Mathematics), killed in the World Trade Center terrorist attack on 11 September 2001. The octacube encodes a rich variety of structures arising in advanced areas of Mathematics and Physics (Quantum Field Theory). For details, see Adrian Ocneanu's commentary and the Penn State octacube page.

Tuesday, February 3, 2009

Professor Solzhenitsyn!

In 1941, Alexandr Solzhenitsyn (1918-2008) graduated from Rostov University (currently Southern Federal University) - where he studied Mathematics and Physics. In this picture he is shown teaching mathematics to his children. For more details, see the "Solzhenitsyn mathematician" note from the "Math in the Media" magazine.

Saturday, January 31, 2009

Another quick "2009" stuff

Let



and let




be a function satisfying






Then f has at least one fixed point, that is, there exists an element x in X such that f(x)=x.

Indeed, it is not hard to see that f is a bijection and induces a permutation of X in which all cycles are either of length 3 or 1 (those of length one correspond to the fixed points of f ). Since 2009 is not divisible by 3, there must be a cycle of length 1.

A complicated way of characterizing the constant functions

Show that the constant functions are the only continuous functions




satisfying






for all real numbers x,y.

Wednesday, January 28, 2009

Squares and walks


The (quasi-) random walk represented in the picture corresponds to the cubic polynomial
f(X) = X^3-X-1 mod 2003.
Every step is a unit step. The n-th step is made to the right if f(n) is a perfect square modulo 2003, and to the left, if f(n) is a non-square.

Sunday, January 25, 2009

Factorials and squares

If N > 1, then N! is not a perfect square.

Indeed, let N > 1 and let p be the largest prime that is less than or equal to N. Then 2p cannot be less than or equal to N - otherwise, a prime q greater than p and less than 2p (such a q exists by Bertrand's theorem), would be a prime greater than p that is less than or equal to N. Thus p defined as above appears with an exponent of 1 in the prime decomposition of N! and therefore N! cannot be a perfect square if N > 1.

Tuesday, January 20, 2009

Un sir neperiodic

Sa consideram sirul binar a_n, n=0,1,2,... definit dupa cum urmeaza:

a_n=0, daca scrierea lui 2^n in baza 10 are un numar par de cifre, si a_n=1, in caz contrar.
Sa se arate ca {a_n} nu este "eventual periodic" (nu exista un intreg pozitiv k astfel incat egalitate a_{n+k}=a_n are loc pentru orice n suficient de mare). Aceasta problema (plus variatii pe aceeasi tema) a constituit o tema de "undergraduate research" pe care am propus-o unui student, acum 6 ani. Este o modalitate frumoasa de a introduce teorema de distributie uniforma in [0,1] a partilor fractionare ale multiplilor unui numar irational.

Saturday, January 17, 2009

On Putnam A1/2008






This is problem A1 from the 2008 Putnam Exam.
The proof is quite straightforward:






















Thursday, January 15, 2009

"modulo n"...

Pentru fiecare n > 1 "inelul intregilor modulo n" Z/nZ consta din 0,1,...,n-1, adica toate resturile ce pot fi obtinute la impartirea cu n. Aceste elemente nu sunt "numere intregi obisnuite", similaritatea in notatie putand fi inselatoare. Astfel, "0"-ul lui Z/nZ reprezinta toti intregii care dau restul 0 la impartirea cu n, "1"-ul lui Z/nZ reprezinta toti intregii care dau restul 1 la impartirea cu n, si asa mai departe. Z/nZ este un univers aparte, in care se definesc o "adunare modulo n" si o "inmultire modulo n". Ideea este simpla: sa ne imaginam ca adunam/inmultim "normal" si, in cele din urma, pentru a identifica rezultatul adunarii/inmultirii in Z/nZ vom scrie numai restul adunarii/inmultirii "normale" la impartirea cu n. De exemplu: in Z/3Z = {0,1,2} avem 1+2=0, 2+2=1, 2^9=2, iar (X+Y)^3=X^3+Y^3 este o identitate valida! Putem considera "19" ca element al lui Z/3Z? Sigur! Iarasi, pentru a-l identifica pe 19, vom lua restul lui 19 la impartirea cu 3 - astfel, 19=1 in Z/3Z. Asemenea identificari sunt uneori foarte utile. De exemplu care dintre elementele 0,1,...,8 ale lui Z/9Z il reprezinta pe 11^99? In sfarsit, ca aplicatie la ecuatii in numere intregi, sa se arate ca ecuatia 3*X^2-Y^2=1 nu are solutii in numere intregi. 

Wednesday, January 14, 2009

2009

Since we are at the beginning of 2009, I will try to break the ice with a list of problems involving the number 2009.
  1. Factor 2009.
  2. Write 2009 as a sum of two squares: 2009=x^2+y^2 with integers x and y.
  3. If x and y are integers and if x^2+y^2 is a multiple of 2009, is it true that both x and y must be multiples of 7?
  4. How many zeros are there at the end of 2009! ?