Autor(es):
Azevedo, Assis 
; Carvalho, Maria ; Machiavelo, António
Data: 2012
Identificador Persistente: http://hdl.handle.net/1822/24771
Origem: RepositóriUM - Universidade do Minho
Assunto(s): Sistemas dinâmicos discretos;; Função tecto; Densidade; Cobertura; Discrete dynamical system; Ceiling function; Density; Covering system
Descrição
Fixado $M\in \N$, escolhamos aleatoriamente $a_1\in \N$ e consideremos $M_1=\frac{M}{(M,a_1)}$. Repita-se este procedimento, seleccionando ao acaso $a_2$ e definindo
$M_2=\frac{M_1}{(M_1,a_2)}$, e assim sucessivamente. Dados $M, n\in\N$, qual é a probabilidade, digamos $\mathcal{P}(n,M)$, de ser $M_n=1$? Tem-se $\mathcal{P}(1,M)=\frac{1}{M}$ e a relação de recorrência $\mathcal{P}(n+1,M)=\sum_{dM}\frac{\varphi(d)}{M} \mathcal{P}(n,d)$, onde $\varphi$ é a função de Euler. O que implica que, com probabilidade um, $M_n=1$ para algum $n\in \N$. O sistema dinâmico discreto associado à aplicação $\cchi:\Q\to \Q$ dada por $\cchi(x)= x\ceil{x}$ simula o comportamento deste processo aleatório, tratando-se agora de saber se a órbita por $\cchi$ de qualquer racional de $[1, +\infty[$ entra em $\Z$. Em \cite{A}, provou-se que o conjunto das fracções irredutíveis com denominador
$M$ cujas órbitas entram em $\Z$ no $n$-ésimo iterado é uma união disjunta de classes de congruência módulo $M^{n+1}$. Este resultado sugeriu um algoritmo eficiente para decidir se um racional está nesta união e, do número daquelas classes, deduzimos que, com probabilidade $1$, a órbita de um racional de $[1, +\infty[$ entra em $\Z$. Given M 2 N, suppose one randomly chooses a1 2 N, sets M1 = M
(M,a1) ,
then repeats the process by randomly sorting out a2 and letting M2 = M1
(M1,a2) , and
so on. Given M, n 2 N, what is the probability, say P(n,M), that Mn = 1?
Clearly P(1,M) = 1
M and the numbers P(n,M) satisfy the recurrence relation
P(n+1,M) = P
dM
'(d)
M P(n, d), where ' is the Euler function. This implies that,
with probability one, Mn = 1 for some n. The map : Q ! Q given by (x) =
xdxe induces a deterministic dynamical system modeling this random behavior.
The question we address now is whether the orbit by of any rational bigger than
1 enters Z. In [1] we proved that the set of irreducible fractions with denominator
M whose orbits by reach an integer in exactly n iterations is a disjoint union of
congruence classes modulo Mn+1. The proof of this result suggested how to build
an efficient algorithm to decide if an orbit fails to hit an integer before a prescribed
number of iterations have elapsed. Besides, from the number of those classes, we
deduced that, with probability 1, the orbit of a rational in [1,+1[ enters Z.
palavras-chave: sistemas dinâmicos discretos; função tecto; densidade; cobertura
