Operators using the floor function |_ z _|:
Let the golden ratio be t = (sqrt(5)+1)/2 and s = sqrt(2).
Further Fib(n) = (t^n - (-t)^(-n))/sqrt(5) is the nth Fibonacci number.
Problem A: [FPS90 Thm 2]
Define the dyadic operator $ over the integers as
m $ n = m*n - m*|_t*n_| - |_t*m_|*n
Show that $ is associative.
Problem B: [FPS90 Thm 4 special case k = 1]
Define the dyadic operator @ over the integers as
m @ n = m*n + |_t*m_|*|_t*n_|
Show that @ is associative.
Problem C: [FPS90 Thm 4]
Define the dyadic operator @_k over the integers as
m @_k n = (-1)^(k+1)*( Fib(k-2)*m*n + Fib(k-1)*(m*|_t*n_| + |_t*m_|*n) + Fib(k)*|_t*m_|*|_t*n_| )
Show that @_k is associative for k>=0.
Problem D: [FPS90 section 6 with d=2]
Define the dyadic operator @ over the integers as
m @ n = - m*|_s*n_| - |_s*m_|*n
Show that @ is associative.
Problem E: [FPS90]
Define the dyadic operator @ over the integers as
m @ n = e*( m*n + 2*m*|_t*n_| + 2*|_t*m_|*n + 3*|_t*m_|*|_t*n_| )
with e in {-1, -2, -3, -4, -5, -6, -7}.
Show that @ is associative.
Problem F: [GKP94, 2nd Ed., margins of Exc. 6.82], [Knu88]
Define the dyadic operator @ over the integers as
m @ n = m*n + m*|_(n+1)/t_| + |_(m+1)/t_|*n
= 1 - (m+1)*(n+1) + m*|_t*(n+1)_| + |_t*(m+1)_|*n
Show that @ is associative.
Note A:
Show { m $ n } = { |_t*m_| } * { |_t*n_| }
with {x} := x - |_x_|.
Note B:
Show m @ n = m $ 1 $ n with operator $ of problem A.
Show that (k @ m) @ n = k @ (m @ n) = k*m*n + k*|_t*m_|*|_t*n_| +
|_t*k_|*m*|_t*n_| + |_t*k_|*|_t*m_|*n + |_t*k_|*|_t*m_|*|_t*n_|.
Note C:
Let p = m @_k n then
(A) { p }/t^k = { m }/t^k * { n }/t^k for k >= 0
(B) p = m $ ((-1)^(k+1)*Fib(k)) $ n for k >= 1
Special cases: $ = @_0.
Note F: Fibonacci multiplication @
Each positive integer can be written as the sum
of distinct Fibonacci numbers. A set F with
m = \Sum_{i in F} Fib(i)
is called a Fibonacci representation of m.
This representation is not unique, but it
will be if no adjacend integers are allowed
and the indices are >= 2. This is the
Zeckendorf representation [GKP88 (6.113)] we name FIB(m).
Example: 20 = 13 + 5 + 2 = Fib(7) + Fib(5) + Fib(3).
Therefore FIB(20) = {3, 5, 7}. Show that
m @ n = \Sum_{(i,j) in FIB(m)xFIB(n)} Fib(i + j)
References:
Fra94: Aviezri S. Fraenkel;
Iterated floor function, algebraic numbers, discrete chaos,
Beatty subsequences, semigroups.
Trans. Am. Math. Soc. 341, No.2, 639-664 (1994).
Zbl 808.05008
Sect 7. Associativity and Closure of some Binary Operations
FPS90: A. S. Fraenkel, H. Porta, K. B. Stolarsky;
Some arithmetical semigroups,
In: Analytic Number Theory.
Proceedings of a Conference in Honor of Paul T. Bateman,
PM 85 (1990) 255-264
Ed. Berndt, Diamond, Halberstam, Hildebrand.
MR 92h:11004
GKP94: Ronald L. Graham, Donald E. Knuth, Oren Pataschnik;
Concrete Mathematics,
Addison Wessley, Reading (1994) 2nd Ed.
Chap 3: Integer Functions
Sect 3.1: Floors and Ceilings
Sect 3.2: Floor/Ceiling Applications
Sect 3.3: Floor/Ceiling Recurrences
Sect 3.4: Mod: the Binary Operation
Sect 3.5: Floor/Ceiling Sums
- Exc. 6.82 Fibonacci addition
(Fibonacci multiplication (2nd Ed. only)
mentioned in the margins)
Knu88: Donald E. Knuth;
Fibonacci multiplication,
Applied Mathematics Letters 1 (1988) 57-60
Reviews:
92h:11004 11A05 (20M14)
Fraenkel, A. S.(IL-WEIZ-AM); Porta, H.(1-IL); Stolarsky, K. B.(1-IL)
Some arithmetical semigroups.
Analytic number theory (Allerton Park, IL, 1989), 255--264,
Progr. Math., 85,
Birkh"auser Boston, Boston, MA, 1990.
This paper is a summary of results of the authors on the construction
of semigroup structures on the integers. A typical example is
$m\dagger n\coloneq mn-n[m\phi]-m[n\phi]$, where $\phi=(1+\sqrt5)/2$.
It has the amusing property that $\{(n\dagger m)\phi\}=\{n\phi\}\{m\phi\}$,
which implies that the set of numbers $\{n\phi\}$ is closed under ordinary
multiplication. Many other examples are given.
\{For the entire collection see MR 91h:11001\}.
92d:11020 11C20 (20M10)
Porta, Horacio A.(1-IL); Stolarsky, Kenneth B.(1-IL)
Wythoff pairs as semigroup invariants.
Adv. Math. 85 (1991), no. 1, 69--82.
The authors' main result is that a certain set of $3\times 3$ matrices with
integer entries is closed under multiplication. Four of the nine entries in
such a matrix involve $[n\varphi]$, where $\varphi=\frac 12(1+\sqrt 5)$ is
the golden ratio, and $[x]$ denotes the greatest integer function. The proof
of this result is based on the properties of semigroups.
Reviewed by Neville Robbins
97g:11024 11B83 (15A30 20M99)
Stolarsky, Kenneth B.(1-IL)
Positive factors of Wythoff matrices.
Semigroup Forum 53 (1996), no. 3, 271--277.
Let $\phi=(\sqrt{5}+1)/2$ and set $a(n)=[n\phi]$, $b(n)=[n\phi\sp 2]$.
The pairs $(a(n),b(n))$ are the winning positions in Wythoff's game.
(See E. R. Berlekamp, J. H. Conway and R. K. Guy [ Winning ways for your
mathematical plays. Vol. 1, Academic Press, London, 1982; MR 84h:90091a;
Vol. 2; MR 84h:90091b] for a discussion of this game.)
$\sigma(n)=\left[\smallmatrix n&a(n)\\a(n)&b(n)\endsmallmatrix\right]$
is called the $n$th Wythoff matrix. Let $S=\{\sigma(n)\colon n\geq 1\}$.
It turns out that $S$ is a multiplicative subsemigroup of $M$, the semigroup
of all nonsingular $2\times 2$ matrices with positive integral entries.
Several papers, many of them by the author and his collaborators, have been
published about the semigroup $S$. In this paper, the author continues these
investigations. Several results are established. The main one is the following:
Theorem. Let $G\in M$. Then there exist $P,Q\in M$ such that $PGQ\in S$.
Reviewed by H. L. Abbott
Fraenkel, Aviezri S.
Iterated floor function, algebraic numbers, discrete chaos, Beatty
subsequences, semigroups. (English)
Trans. Am. Math. Soc. 341, No.2, 639-664 (1994).
Zbl 808.05008
For a real number $\alpha$, the floor function $\lfloor \alpha \rfloor$ is the
integer part of $\alpha$. The sequence $\{\lfloor m \alpha \rfloor : m = 1, 2,
3,\dots \}$ is the Beatty sequence of $\alpha$. Identities are proved which
express the sum of the iterated floor functional $A\sp i$ for $1 \le i \le n$,
operating on a nonzero algebraic number $\alpha$ of degree $\le n$, in
terms of only $A\sp 1 = \lfloor m \alpha \rfloor$, $m$ and a bounded term.
Applications include discrete chaos (discrete dynamical systems), explicit
construction of infinite non chaotic subsequences of chaotic sequences,
discrete order (identities), explicit construction of nontrivial Beatty
subsequences, and certain arithmetical semigroups. Beatty sequences have
a large literature in combinatorics. They have also been used in nonperiodic
tilings (quasicrystallography), periodic scheduling computer vision (digital
lines), and formal language theory.
--
mailto:Torsten.Sillke@uni-bielefeld.de
http://www.mathematik.uni-bielefeld.de/~sillke/