Acurtar o cálculo da exponenciación modular

 por Andrés Ventas

Acurtar o cálculo da exponenciación modular

O cálculo do expoñente modular é un tema moi tratado debido ao seu uso en criptografía e evidentemente o seu uso nas claves de internet.

A exponenciación modular consiste en calcular unha expresión do tipo $$b^e\equiv r(\mathrm{mod}m),$$ isto é, unha base $b$ elevada a un expoñente $e$ módulo $m$ onde temos que calcular o residuo $r$ que será un enteiro entre $0$ e $m-1$.

A cuestión problemática é que para criptografía úsase un expoñente moi grande.

Os métodos máis coñecidos son: método directo, o de memoria eficiente e o máis rápido sería o de expoñente binario. Aquí imos ver un novo método "de aproximación ao módulo" que nas probas realizadas resulta sempre máis curto que o do expoñente binario (non tanto como parecía a priori).

Os tres últimos métodos usan a propiedade modular de que o módulo do produto é igual ao produto dos módulos: $$(b\cdot b_1)\mathrm{mod}m=(b\mathrm{mod}m)\cdot (b_1\mathrm{mod}m)$$ Imos mostrar os 4 métodos co exemplo da wikipedia Modular exponentiation $$4^{13}\equiv r(\mathrm{mod}497)$$

Non esquezamos que se a base é maior que o módulo pódese aplicar primeiro o módulo á base, por exemplo: ${501}^{13}\equiv c(\mathrm{mod}497)\text{ implica }{4}^{13}\equiv c(\mathrm{mod}497)$. Isto sería común para todos os métodos.

O método directo

O método directo sería obter $b^e$ e calcular o seu residuo, así $$4^{13}=67108864\mathrm{mod}497=445.$$ Evidentemente para expoñentes grandes (veremos algún exemplo posterior) este método ten problemas coa capacidade da memoria e produce unha división longa computacionalmente para calcular o residuo.

Método de memoria eficiente

O método de memoria eficiente vai calculando o módulo paso a paso aumentando o expoñente nunha unidade, isto é, multiplicando pola base en cada paso: $$\begin{array}{rl}4& \mathrm{mod}497=4\\ 16& \mathrm{mod}497=16\\ 64& \mathrm{mod}497=64\\ 256& \mathrm{mod}497=256\\ 1024& \mathrm{mod}497=30\\ 30\cdot 4=120& \mathrm{mod}497=120\\ & \text{e igualmente ata o último paso}\dots \\ 484\cdot 4=1936& \mathrm{mod}497=445\end{array}$$

Isto require 13 pasos que evidentemente para un expoñente máis grande dá un número de operacións non asumíbel.

Método de expoñente binario

Nos documentos consultados é o método actualmente considerado maís rápido. O método consiste en transformar o expoñente a binario e ir calculando en función dos 0 e 1 do expoñente en binario, temos dúas variábeis $x$ e $R$, en $x$ imos gardando o valor a calcular e en $R$ o resultado que se vai reseteando cada vez que temos un bit $1$. Ímolo ver co noso exemplo: $$\begin{array}{rl}& R\leftarrow 1(=b^0)\text{ e }x\leftarrow b=4.\\ & \text{Paso 1) o bit 1 é 1, así que se estabelece }\\ & R\leftarrow R\cdot 4\equiv 4(\mathrm{mod}497);\\ & \text{ agora }x\leftarrow x^2(=b^2)\equiv 4^2\equiv 16(\mathrm{mod}497).\\ & \text{ Paso 2) o bit 2 é 0, polo que non recalculamos ''R'';}\\ & \text{ así }x\leftarrow x^2(=b^4)\equiv {16}^2\equiv 256(\mathrm{mod}497).\\ & \text{ Paso 3) o bit 3 é 1, así que recalculamos ''R''}\\ & R\leftarrow R\cdot x(=b^5)\equiv 4\cdot 256\equiv 30(\mathrm{mod}497);\\ & \text{ agora }x\leftarrow x^2(=b^8)\equiv {256}^2\equiv 429(\mathrm{mod}497).\\ & \text{ Paso 4) o bit 4 é 1, así que recalculamos ''R''}\\ & R\leftarrow R\cdot x(=b^{13})\equiv 30\cdot 429\equiv 445(\mathrm{mod}497);\end{array}$$ Algoritmo moi interesante, pasamos de 13 pasos a 4 e como a rebaixa de pasos é logarítmica con un expoñente máis grande a efectividade é enorme.

Método de aproximación modular

Consiste en procurar a potencia $e_1$ de $b$ máis próxima ao módulo $m$ (sería válido superiormente ou inferiormente), calcular o módulo con este resultado $b^{e_1}\equiv c_1(\mathrm{mod}m)$ e calculando a división enteira dos espoñentes $\frac{e}{e_1}\text{ con }e=e_1\cdot d+r$ transformamos a expresión orixinal con cifras moito menores. Para o noso exemplo: $$\begin{array}{rl}& 4^5=1024\text{ e }13=2\cdot 5+3\\ & 1024\equiv 30(\mathrm{mod}497).R=30,x={30}^2\cdot 4^3\\ & {30}^2\equiv -94(\mathrm{mod}497).\\ & -94\cdot 64=6016\equiv -52(\mathrm{mod}497).\\ & R=497-52=445.\end{array}$$ Este método sen usar o algoritmo dá moitas posibilidades de reorganizalo para acurtar e isto sería un tema de estudo para estabelecer esas melloras metodicamente, imos ver o anterior módulo $7$: $$\begin{array}{rl}& 4^{13}=2^{26}\equiv c(\mathrm{mod}7)\\ & 2^3\equiv -1(\mathrm{mod}7)\text{ e }26=8\cdot 3+2\\ & (-1{)}^8\cdot 4\equiv 4(\mathrm{mod}7).\end{array}$$ E mellor aínda, aplicando directamente Fermat: Se $a$ é un enteiro e $p$ é un primo que non divide $a$, daquela $a^{p-1}\equiv 1(\mathrm{mod}p).$ (Emanuel Lazar) notes06-3.pdf Temos: $$\begin{array}{rl}& 2^6\equiv 1(\mathrm{mod}7)\text{ e }26=6\cdot 4+2\\ & (1{)}^4\cdot 4\equiv 4(\mathrm{mod}7).\end{array}$$ Imos comparar con algúns exemplos vistos na rede: fast modular exponentiation (Khan Academy) $$\begin{array}{rl}& 7^{256}\equiv c(\mathrm{mod}13)\text{ daquela }{7}^{12}\equiv 1(\mathrm{mod}13)\text{ e }256\equiv 4(\mathrm{mod}12)\\ & 7^4(\mathrm{mod}13)\equiv (-3{)}^2(\mathrm{mod}13)=9(\mathrm{mod}13).\end{array}$$ Por último temos o teorema de Fermat-Euler: Se $a$ e $n$ son enteiros positivos coprimos daquela $a^{\varphi (n)}\equiv 1(\mathrm{mod}n).$ Teorema de Euler (Galipedia) Onde $\varphi (n)$ é a función totiente de Euler. Sen usar ese teorema, pois a función totiente non é fácil de calcular salvo para números primos, e para números grandes é difícil saber se un número é primo, imos calcular o exemplo que aparece no artigo do teorema de Euler (ou Fermat-Euler) da Galipedia: $$\begin{array}{rl}& 7^{222}\equiv c(\mathrm{mod}10)\text{ así temos }{7}^2=49\equiv -1(\mathrm{mod}10)\text{ e }222=2\cdot 111+0.\\ & (-1{)}^{111}(\mathrm{mod}10)\equiv -1(\mathrm{mod}10)\equiv 9(\mathrm{mod}10).\end{array}$$

Bibliografia

1. Modular exponentiation (Wikipedia)
2. Exponenciación amodular (Galipedia)
3. (Emanuel Lazar) notes06-3.pdf
4. fast modular exponentiation (Khan Academy)
5. Teorema de Euler (Galipedia)

Teorema de Hall: o teorema dos matrimonios

 Na entrada anterior presentaramos o seguinte resultado

Teorema do matrimonio de Hall. Dado un grafo bipartito $G=(X,Y)$, unha condición necesaria e suficiente para que $X$ teña un emparellamento perfecto (condición de Hall) é que  $\mathrm{\forall }A\subset X$ se verifique que $\left|A\right|\le \left|N\left(A\right)\right|$

Segundo a Wikipedia o teorema de Hall recibe o nome de teorema do matrimonio debido a un artigo do ano 1950 no que Halmos e Vaugan se refiren ao teorema para tratar a seguinte cuestión:

"Supoñamos que un grupo de mozos [...] coñece un conxunto finito de mozas. Baixo que condicións é posible que cada un deles se case cunha das súas coñecidas?"

Desde un punto de vista da sociedade actual o enunciado do problema fica algo desfasado. Con todo, o problema pode levarnos a unha ampliación do noso punto de vista matemático. Para iso seguiremos o libro de Gilbert Strang, Introduction to applied mathematics (Wellesley-Cambidge Press 1986).

Dadas $n$ señoritas , que por seren de xénero feminino identificaremos por $f_1,f_2,...,f_n$ e outros tantos cabaleiros $c_1,c_2,...,c_n$ estableceremos unha matriz $A=\left(a_{ij}\right)$ onde $a_{ij}=1$ se $f_i$ e $c_j$ están dispostos a casar. No caso contrario escribiremos $a_{ij}=0$. Se for posible establecer $n$ matrimonios significa que hai un emparellamento perfecto no grafo asociado. Vexamos un exemplo no que puidemos establecer $4$ matrimonios que son os que aparecen marcados nun recadro.

Porén no seguinte caso non é posible celebrar máis que tres bodas: $(f_1,c_3),(f_2,c_4)$ e $(f_3,c_2)$:

Esta matriz dá lugar ao seguinte grafo no que resaltamos con arestas grosas os tres matrimonios:

Se escollo as tres últimas filas $\{f_2,f_3,f_4\}$ comprobo inmediatamente que a súa veciñanza está formada por só dúas columnas $\{c_2,c_4\}$. Isto significa que non se verifica a condición de Hall. De aí que non poidan establecerse $4$ matrimonios.

Voulle chamar liña a unha fila ou columna. Comprobarás que marcando as tres liñas rodeadas en azul teño cubertos todos os $1s$ da matriz $A^{\prime }$. Isto vén a conto do seguinte teorema que é equivalente ao de Hall:

Terorema de Köning-Egerváry. Nunha matriz de $0s$ e $1s$ o máxino número de matrimonios é igual ao mínimo número de liñas que cubren todos os $1s$

Todo isto podémolo relacionar con outras cousas coñecidas. Consideremos a matriz $A$ como un taboleiro de xadrez de dimensións $n\times n$ onde cada elemento é un escaque. Propoñemos o reto de colocar o maior número posible de torres sen que se ameacen entre sí coa restrición de que só está permitido colocalas nos escaques marcados con $1$. Evidentemente o xogo é esencialmente o mesmo problema que o do matrimonio.

Imos dar algo máis de terminoloxía para ampliar a perspectiva deste resultado. Unha cobertura $K$ dun grafo é un conxunto de vértices do grafo tal que todas as arestas do grafo teñen polo menos un vértice en $K$. Sempre será interesante obter unha cobertura mínima, isto é, aquela que teña o menor número de vértices posible. A seguinte figura pode aclararnos a situación. Nela están marcados en negro os vértices que forman a cobertura.

Os emparellamentos podemos consideralos como coberturas. Ademais dado calquera emparellamento $M$ e calquera cobertura $K$, verificarase claramente que $\left|M\right|<\left|K\right|$. Con estes vimbios podemos reescribir o

Teorema de Köning-Egerváry. Nun grafo bipartito o número de arestas dun emparellamento máximo é igual ao número de vértices dunha cobertura mínima.

Tamén podemos afrontar o problema desde un punto de vista alxébrico. Volvendo ás matrices, do que se trata é de obter o seu rango. Se hai unha fémina á que non lle guste ningún cabaleiro teremos unha fila só con $0s$. Neste caso xa sabemos que o determinante da matriz será nulo. Como todos os valores son $1s$ e $0s$ o teorema de Hall establece que para que poidan celebrarse $n$ matrimonios, ou o que é o mesmo, que a matriz dos matrimonios sexa regular,  vai ter que verificarse calquera das tres seguintes condicións equivalentes

• Non existe unha submatriz de $0s$ de dimensión $r\times s$ con $r+s>n$
• A cada subconxunto de $1\le r\le n$ mozas lles gustan polo menos $r$ mozos
• A cada subconxunto de $1\le s\le n$ mozos lles gustan polo  menos $s$ mozas

Na seguinte entrada veremos máis aplicación do teorema de Hall.

O teorema de Hall. O caso dos trucos de maxia de Cheney

Na entrada "Criptografía e maxia no Losada", onde relataba algúns aspectos da charla que viñeron impartir á Estrada Nicanor Alonso e Miguel Mirás, expliquei o truco de maxia das 5 cartas de Cheney. Este truco xa fora tratado por Martin Gardner pois todo o interesante xa foi tratado antes por Martin Gardner. Efectivamente unha versión do truco aparece no libro  El ahorcamiento inesperado y otros entretenimientos matemáticos (Alianza Editorial, 1991). Neste caso o mérito é aínda maior porque esta versión foi presentada nun congreso de magos, isto é, diante dunha audiencia incómoda para quen realiza o truco pois esa audiencia non estaba disposta a deixarse enganar.

O (mate)mago que presentaba o xogo era Victor Eigen. Un espectador, que non era outro que Martin Gardner, ofreceu a súa propia baralla para que o mago non tivese posibilidade de marcar as cartas. O espectador escolleu 5 cartas e (isto é unha diferenza importante coa versión relatada aquí) escolleu tamén cal desas 5 cartas se debía adiviñar. O único que podía facer o mago era ordenar as outras $4$ cartas. Nesa orde leváronllas á muller de Eigen, que se hospedaba nunha habitación do hotel que albergaba o congreso. E a muller acertou a carta escollida! Como podía ser?  $4$ cartas só podemos ordenalas de $24$ formas distintas. Parecía imposible que Eigen e a súa muller poidesen elaborar un código para as 52 cartas.

A resposta é a seguinte. En primeiro lugar, como á señora Eigen lle entregaban $4$ cartas xa non tiña que buscar a carta escollida entre as $52$ da baralla. Quedábanlle $52-4=48$ pero os Eigen só podían elaborar un código para a metade deste montón, $24$. A trampa era que o matrimonio reservara dúas habitacións contiguas e Victor non desvelou o número da habitación ata que Gardner escolleu a carta que debía adiviñar a señora Eigen. Cando Gardner petou nunha das portas para entregar as $4$ cartas, a muller de Victor puido descartar $24$

O truco orixinal

Volvamos ao truco orixinal, que apareceu nun artigo do ano 1950 na revista Math Miracles e no que lle atribuían a invención a Fitch Cheney. Lembremos as condicións. O mago marcha da habitación. Un espectador escolle $5$ cartas e o axudante do mago dálle a volta a unha desas $5$ cartas e colócaa á dereita das outras $4$ que fican cara arriba. Como é o axudante quen escolle a carta a adiviñar, podemos usar este feito para dar máis información ao mago-vidente. Na experiencia que relatamos da adiviñación no IES Antón Losada o axudante escollía unha carta do mesmo pau que a oculta. Isto reduce as posibilidades nun factor $4$ pero pode facerse mellor e as $P_4=4!=24$ posibilidades de ordenación das cartas poden chegar a multiplicarse por un factor $5$ á hora codificar toda a información. Ademais, ao estaren á vista $4$ cartas o mago sabe que a oculta non pode ser ningunha desas. De aí que o truco das $5$ cartas permitiría realizar a adiviñación nun mazo de $5\cdot 4!+4=5!+4=124$ cartas. Neste artigo, Using a card trick to teach discrete mathematics,  Shai Simonson e Thara S. Holm mostran como facelo. Daquela podemos considerar en xeneralizar o truco para un mazo de $m$ cartas do que extraemos $n$ e despois, de entre estas $n$ o axudante escolle unha para que sexa a carta oculta. Así o mazo podería ter $m=n\cdot (n-1)!+n-1=n!+n-1$ cartas [1]. Na seguinte táboa mostramos os primeiros valores.

$n$	$m=n!+n-1$
$1$	$1$
$2$	$3$
$3$	$8$
$4$	$27$
$5$	$124$
$6$	$725$

Claro que o valor de $m$ podería ser menor. Se podemos establecer unha codificación para os valores de $m$ dados na táboa anterior, é evidente que tamén se poderá facer se o tamaño do mazo é inferior a $m$. Por exemplo, no caso relatado cando presentamos o truco de Cheney, o mazo era normal, tiña $m=52$ cartas, cando para $n=5$, tal e como queda establecido nesta táboa, poderiamos facer o truco para un total de $m=124$ cartas. 

Coa finalidade de afacernos ao problema, estudaremos os primeiros casos.  Para $n=2$ e $m=3$ a codificación é trivial.

12	13	23
1	3	2

As cartas ocultas son as que aparecen en branco con fondo negro. Así, se o espectador escolle o par $1,2$, o axudante dálle a volta á carta $2$ e o mago ao ver cara arriba a carta $1$ xa sabe que está oculto o $2$ 

Para o seguinte valor, $n=3$, $m=8$ as cousas xa se complican bastante. O espectador terá $C_{8,3}=(\genfrac{}{}{0ex}{}{8}{3})=56$ formas posibles de escoller 3 cartas. Agora o axudante debe deixar dúas delas cara arriba nunha determinada orde. Hai un total de $A_{8,2}=56$ arranxos, isto é, formas de escoller $2$ cartas ordenadas no mazo de $8$. Os valores coinciden, pero será posible establecer un código para cada caso? Teñamos presente que o código está formado por dúas cartas ordenadas, pero esas dúas cartas teñen que escollerse entre as $3$ determinadas polo  espectador. Neste caso pódese facer tal e como vemos na seguinte táboa. Se o espectador colleu as cartas $123$ o axudante tapa a última e deixa as outras na orde indicada na segunda fila $1,2$. Se a orde fose $2,1$ o mago sabería que a carta oculta tería que ser un $4$.

123	124	134	135	145	146	125	156
1,2	2,1	1,3	3,1	1,4	4,1	1,5	5.1
126	136	127	137	128	138	234	235
1,6	6,1	1,7	7,1	1,8	8,1	2,3	3,2
245	246	256	257	236	267	237	247
2,4	4,2	2,5	5,2	2,6	6,2	2,7	7,2
238	248	345	346	356	357	367	368
2,8	8,2	3,4	4.3	3,5	5,3	3,6	6,3
347	378	348	358	456	457	467	468
3,7	7,3	3,8	8,3	4,5	5,4	4,6	6,4
147	478	148	458	567	568	157	578
4,7	7,4	4,8	8,4	5,6	6,5	5,7	7,5
158	258	167	678	168	268	178	278
5,8	8,5	6,7	7,6	6,8	8,6	7,8	8,7

Poderemos establecer sempre un código? Ao escoller o código $(1,2)$ para 123 estamos imposibilitando que este código nos identifique os casos 124, 125,... 128 polo que todas estas escollas deben ser codificadas con outros pares ordenados de números que poderían ser $(1,4)$, $(1,5)$,..., $(1,8)$ pero estas novas escollas permitirán establecer un código distinto para as posibilidades que faltan? Haberá algunhas asignacións que nos impidan colocar as últimas identificacións. 

O seguinte caso, o de $n=4$ e $m=27$ xa daría lugar a unha táboa codificadora de $C_{27,4}=(\genfrac{}{}{0ex}{}{27}{4})=A_{17,3}=17550$ elementos.

En xeral o código poderá crearse se hai unha relación biunívoca entre todas as posibles escollas do espectador que suman un total de $C_{m,n}=(\genfrac{}{}{0ex}{}{m}{n})$ posibilidades, e as ordenación de $n-1$ cartas que faga o axudante. Este último valor contabilízase mediante os arranxos $A_{m,n-1}=m\cdot (m-1)\cdot ...\cdot (m-n+2)$. Se igualamos estas expresións:

$$C_{m,n}=(\genfrac{}{}{0ex}{}{m}{n})=\frac{m!}{n!(m-n)!}=A_{m,n-1}=\frac{m!}{(m-n+1)!}$$

Igualando denominadores e operando:

$$(m-n+1)!=n!(m-n)!$$ $$\frac{(m-n+1)!}{(m-n)!}=n!$$ $$m-n+1=n!$$ $$m=n!+n-1$$

Velaí que os dous conxuntos teñen o mesmo cardinal cando a cantidade de cartas do mazo é a que determinaramos previamente en [1]. A cuestión sería entón se se poderá establecer unha codificación da información dada polo protocolo do xogo para poder levalo a cabo en todos os casos. Unha opción sería a de elaborar un algoritmo que cree unha codificación para calquera caso. Esta sería a resposta escollida por un informático. Pero hai un achegamento máis bonito, o derivado do punto de vista matemático. Non nos dá a solución, pero hai un teorema da teoría de grafos que nos permite asegurar a existencia da codificación. O teorema é o seguinte.

Teorema de Hall. Dado un grafo bipartito $G=(X,Y)$, unha condición necesaria e suficiente para que $X$ teña un emparellamento perfecto (condición de Hall) é que  $\mathrm{\forall }A\subset X$ se verifique que $\left|A\right|\le \left|N\left(A\right)\right|$

Cómpre aclarar notación e conceptos para entendermos o teorema. Un grafo $G$ dise bipartito se pode descompoñerse na unión disxunta de dous conxuntos de vértices $X$ e $Y$ tales que os vértices de $X$ só se conectan con vértices de $Y$ (e viceversa). $N\left(A\right)$ fai referencia á veciñanza de $A$, isto é, o conxunto de vértices que están conectados con algún elemento de $A$. As barras verticais indican o cardinal. Un emparellamento $M$ dun grafo $G$ é unha colección de arestas que non teñen ningún vértice en común. Dise que un emparellamento SMS é perfecto se todos os vértices do grafo son extremo dalgunha aresta de $M$.

Consideremos o caso xeral. Temos $m=n!+n-1$ cartas distintas, o espectador escolle $n$ e o axudante dálle a volta a unha delas e ordena as restantes. Imos ver que poderemos establecer unha relación biunívoca (ou emparellamento perfecto) entre as $C_{m,n}$ escollas e as $A_{m,n-1}$ codificacións. Para iso consideramos o grafo bipartito $G=(X,Y)$ onde os vértices de $X$ serán cada unha das posibles combinacións e os de $Y$ cada un dos posibles arranxos. As arestas conectan cada combinación de $n$ elementos de $X$ con todas as posibles ordenacións de $n-1$ elementos desa combinación. Por exemplo na codificación anteriormente estudada para $n=3$ e $m=8$, a combinación 1-2-3 estaría conectada coas permutacións de dous elementos escollidos en {1,2,3}:  (1,2), (2,1), (1,3), (3,1), (2,3) e (3,2). Son un total de $n!=3!=6$ elementos. Da mesma maneira se consideramos un arranxo calquera, como (1,2) veremos que estará conectado coas  6 combinacións 1-2-3, 1-2-4, 1-2-5, 1-2-6, 1-2-7 e  1-2-8. Todos os vértices do grafo terán o mesmo grao, $6$. No caso xeral todos os vértices terán grao $n|$. Este tipo de grafos, nos que todos os vértices teñen o mesmo grao, chámanse grafos regulares. Vexamos que este grafo verifica a condición de Hall.

Efectivamente. Supoñamos que non a verifica, isto é, que existe un subconxunto $A\subset X$ de $k$ vértices que está conectado cun subconxunto de arranxos que ten menos de $k$ vértices. Como o grao de cada elemento é $n!$ a este subconxunto de arranxos, $N\left(A\right)$, deben chegar $n!\cdot k$ arestas. Velaí que polo principio do pombal ten que haber un arranxo ao que cheguen polo menos $n!+1$ arestas, o que entra en contradición con que todos os vértices tiñan grao $n!$.

Conviña decatarse de que non só demostramos a existencia de codificación para calquera truco estilo Cheney senón que acabamos de dar a proba do seguinte resultado:

Corolario. Sexa $G=(X,Y)$ un grafo bipartito regular. Daquela $G$ ten un emparellamento perfecto.

De querermos establecer un código completo para o truco de Cheney orixinal deberiamos cubrir unha táboa con $(\genfrac{}{}{0ex}{}{53}{5})=2.869.685$ celas!. Xa comprobáramos que para esta viaxe non cómpren tales alforxas. Con todo, como para unha escolla de $5$ cartas por parte do espectador temos asegurada a existencia dun código incluso cando o mazo ten $124$ cartas, a cantidade de emparellamentos codificadores para este valor tan baixo ($5$) xa subiría ata un total de $(\genfrac{}{}{0ex}{}{124}{5})=225.150.024$. Pode parecer sorprendente, pero neste pequeno traballo de Michael Kebler establécese un atallo para evitar tremenda tarefa.

O teorema de Hall recibe tamén o nome do teorema do matrimonio.  Na seguinte entrada centrarémonos neste aspecto, na súa relación co problema dos matrimonios. O resultado foi  demostrado polo matemático inglés Philip Hall (1904-1982), gran impulsor da teoría de grupos. Foi un dos participantes en Blettchley  Park no traballo de descodificación de mensaxes durante a II Guerra Mundial. 

Explícoche matemáticas 2025

O concurso Explícoche Matemáticas do SNL da Facultade de Matemáticas da USC pon en evidencia a radicalidade ultra da prohibición do ensino das matemáticas en galego. Xa vai pola súa 13ª edición.

Na edición deste ano do Explícoche Matemáticas o vídeo gañador foi o de Antía Fernández Paulos do IES Castro Alobre (Vilagarcía de Arousa) cun traballo titulado Xogando a aproximar pi:

 

 O segundo premio foi para Adrián Arnoso Bermúdez, Manuel Díaz Sánchez, Saúl López Souto do IES Díaz Pardo (Sada) cun vídeo titulado A tartaruga Fleury

 

Os logaritmos de Napier

Esta entrada do blogue é consecuencia de dúas anteriores. Na primeira delas, Os logaritmos, presentei unha introdución ao concepto tal e como o fago na clase. Na segunda o título delataba o obxectivo. Efectivamente, en Buscando unha base para os logaritmos, partíase do feito de que as progresións xeométricas crecen moi rapidamente mentres que os seus logaritmos, que seguen as leis das progresións aritméticas, teñen un crecemento moito máis lento. Isto levounos a procurar bases moi próximas a $1$ pois teñen unha evolución máis moderada. Con todo non nos atrevéramos a usar bases con números inferiores á unidade. Esta foi a proposta orixinal de John Napier (1550-1617) que dá a coñecer en dúas publicacións: Mirifici Logarithmorum Canonis Descriptio (1616) e a xa póstuma Mirifici logarithmorum canonis constructio (1619).

Nesa altura eran os astrónomos os máis necesitados da nova ferramenta dos logaritmos. Había que facer os cálculos a man e a realización de produtos e divisións eran unha pesada carga. Hoxe en día utilizamos as razóns trigonométricas tomando como base unha circunferencia de raio $1$. Daquela cada autor escollía o tamaño do raio. Como para obter os valores do seno empregaban valores enteiros, canto maior fose o raio, mellores podían ser as aproximacións dos valores que tomaba, Napier decídese por un raio moi grande, $r={10}^7$. En concordancia con isto estableceu como base para os seus logaritmos un valor moi próximo, e menor, á unidade, $k=1-\frac{1}{{10}^7}=1-\frac{1}{r}$. Cal foi o seu procedemento? Napier parte dun esquema formado por dous puntos. Un deles móvese aritmeticamente desde $O$ polo que vai alcanzando os valores $Q_1$, $Q_2$, $Q_3$,... $Q_n$ a intervalos regulares de tempo $t$. Isto é, este punto mantén unha velocidade continua $r$. Ademais, como veremos, Napier tivo o acerto de escoller un valor de $t$ moi pequeno aproximándose ao que unhas décadas máis tarde serían os infinitesimais.Con estes vimbios establecemos sen dificultade que

$$O{Q}_n=n\left(rt\right)$$

Tomemos un segmento $AB$ de medida $r$. Un segundo punto móvese xeometricamente desde $A$, aproximándose ao outro punto $B$ a velocidades proporcionais á distancia a este último. Tomamos $AB=r={10}^7$. Sexa $k$ a constante. A intervalos regulares de tempo $t$ o punto estará en posicións $P_1,P_2,P_3,...,P_n...$ e neses puntos terá velocidades $v_1,v_2,v_3,...,v_n...$ 

Daquela:

$$\frac{B{P}_{n+1}}{B{P}_n}=\frac{v_{n+1}}{v_n}=kB{P}_{n+1}=kB{P}_n$$

$$B{P}_n=B{P}_{n+1}+P_n{P}_{n+1}=B{P}_{n+1}+v_{n}t$$

Das igualdades anteriores dedúcese que:

$$B{P}_n=kB{P}_n+v_{n}t$$ $$(1-k)B{P}_n=v_{n}t$$ $$v_n=\frac{1-k}{t}B{P}_n$$

Tomando $1-k=t$ temos que $v_n=B{P}_n$

Agora, por recursión, imos obter este último valor:

$$B{P}_n=kB{P}_{n-1}=k^{2}B{P}_{n-2}=...=k^{n}B{P}_0=k^{n}BA=r{k}^n$$

Nótese que, como xa comentaramos, $BA=r={10}^7$. 

Napier define o seu logaritmo, ao que chamaremos como fai Juan Havil no  libro Gamma (Pricenton 2003), $NapLog$, da seguinte maneira: $NapLog(B{P}_n)=O{Q}_n$, isto é  $NapLog\left[r{k}^n\right]=n$. Aquí é onde Napier escolle o valor infinitesimal de $t$; toma $t=\frac{1}{r}=\frac{1}{{10}^7}$. Se traducimos a definición de $NapLog$ usando que $r={10}^7$ e que $k=1-t=1-\frac{1}{{10}^7}$ obteremos a seguinte expresión:

$$NapLog\left[{10}^7{(1-\frac{1}{{10}^7})}^n\right]=n$$

Veremos de seguido que o logaritmo de Napier verifica ao seu xeito a propiedade esencial dos logaritmos, isto é, que transforma os produtos en sumas:

$$N_1=r{k}^{n_1};n_1=NapLog\left(r{k}^{n_1}\right)$$  

$$N_2=r{k}^{n_2};n_2=NapLog\left(r{k}^{n_2}\right)$$ 

$$N_1\cdot N_2=r\cdot r\cdot k^{n_1}\cdot k^{n_2}=r\cdot r\cdot k^{n_1+n_2}$$

$$\frac{N_1\cdot N_2}{r}=r\cdot k^{n_1+n_2}$$

$$NapLog\left(\frac{N_1\cdot N_2}{r}\right)=NapLog(r\cdot k^{n_1+n_2})=n_1+n_2=NapLog{N}_1+NapLog{N}_2$$

O logaritmo de Napier desde un punto de vista diferencial

A principios do XVII aínda non nacera o cálculo diferencial. Por iso o achegamento de Napier desenvolveuse polo camiño antes descrito. Que pasaría se a mesma situación descrita ao principio, a dos dous puntos, $Q$ movéndose aritmeticamente e $P$ facéndoo xeometricamente, se lle presentase a un matemático do século seguinte? A súa abordaxe podería vir da man das ecuacións diferenciais. Fagámolo agora así.

Sexa $y=OQ$, verificará $\frac{dy}{dt}=r$

Integrando: $y(t)=rt+c$ con $c$ unha constante que podemos achar mediante a condición inicial: $y(0)=c=r$. Velaí que $y(t)=rt$   [1]. Lembremos esta expresión.

Consideremos agora $AP=r-x$, verificará $\frac{d(r-x)}{dt}=x$ polo que $-\frac{dx}{dt}=x$. Separando as variables: $\frac{dx}{x}=-t$ e integrando: $lnx=-t+c_1$ con $c_1$ unha constante. De aí que $x\left(t\right)=e^{c_1}{e}^{-t}$. 

Chamémoslle $\rho =e^{c_1}$ a esta constante. Así escribiremos $x\left(t\right)=\rho e^{-t}$. Valorando esta expresión en $t=0$: $x\left(0\right)=\rho =r$. En conclusión:

$$x\left(t\right)=r{e}^{-t}[2]$$  

De [1]  obtemos $t=\frac{y}{r}$

De [2] obtemos que $\frac{x}{r}=e^{-t}$ entón $t=-ln\frac{x}{r}=lo{g}_{\frac{1}{e}}\frac{x}{r}$

Igualando 

$$\frac{y}{r}=lo{g}_e\frac{x}{r}$$ $$y=NapLog\left(x\right)=-r\cdot ln\left(\frac{x}{r}\right)[3]$$

Se agora redimensionamos os valores a unha circunferencia de raio $1$:   $X=\frac{x}{r}$ e $Y=\frac{y}{r}$ concluímos que $$\frac{y}{r}=lo{g}_{\frac{1}{e}}\frac{x}{r}$$

Equivalentemente, que o logaritmo de Napier é unha aproximación do logaritmo en base $\frac{1}{e}$:

$$Y=lo{g}_{\frac{1}{e}}X$$

Unha comparación

Querría facer un último comentario sobre todo o anterior. A expresión que obtivemos en [3] para o $NapLog$ é moi aproximada á que nos proporcionou Napier orixinalmente. Para comprobalo ímolas comparar. Lembremos a definición de Napier:

$$NapLog\left(x\right)=NapLog\left[r{(1-\frac{1}{r})}^n\right]=n$$

Está claro que tomamos $x=r{(1-\frac{1}{r})}^n$. Despexemos $n$ tomando logaritmos neperianos:

$$\frac{x}{r}={(1-\frac{1}{r})}^n$$ $$ln\left(\frac{x}{r}\right)=ln{(1-\frac{1}{r})}^n$$ $$ln\left(\frac{x}{r}\right)=n\cdot ln\left(\frac{r-1}{r}\right)$$ $$n=NapLog\left(x\right)=\frac{1}{ln\left(\frac{r-1}{r}\right)}ln\left(\frac{x}{r}\right)[4]$$

Repetimos deseguido a fórmula obtida usando ecuacións diferenciais $$y=NapLog\left(x\right)=-r\cdot ln\left(\frac{x}{r}\right)[3]$$

En [3] e en [4] temos dúas fórmulas distintas para o $NapLog$, diferéncianse no coeficiente de $ln\left(\frac{x}{r}\right)$. Para comparalas calcularemos $q$, o cociente deses coeficientes:

$$q=-r:\frac{1}{ln\left(\frac{r-1}{r}\right)}=-r\cdot ln\left(\frac{r-1}{r}\right)=ln{\left(\frac{r-1}{r}\right)}^{-r}=ln{\left(\frac{r}{r-1}\right)}^r$$

Tendo en conta que $r$ é un número moi grande, para ter unha aproximación de $q$ calcularemos o límite no infinito da expresión á que se lle aplica o logaritmo neperiano. É un deses límites da forma $1^{\mathrm{\infty }}$ que se traballan na materia de Matemáticas II, en 2º de bacharelato. $$\underset{r\to \mathrm{\infty }}{lim}{\left(\frac{r}{r-1}\right)}^r=e^{\lambda }$$

Con $\lambda =\underset{r\to \mathrm{\infty }}{lim}r(\frac{r}{r-1}-1)=\underset{r\to \mathrm{\infty }}{lim}r\frac{1}{r-1}=1$

De aí que $q\simeq \underset{r\to \mathrm{\infty }}{lim}ln{\left(\frac{r}{r-1}\right)}^r=ln{e}^1=1$

En efecto, o valor numérico de $q$ será:

$$q=ln{\left(\frac{r}{r-1}\right)}^r=ln{\left(\frac{{10}^7}{{10}^7-1}\right)}^{{10}^7}=1,00000005000000333333358333335333333500000014285...$$

En conclusión, o logaritmo orixinal de Napier era case o logaritmo en base $\frac{1}{e}$

Relación entre series infinitas, fraccións continuas teito e constantes. Series hiperxeométricas. Final.

por Andrés Ventas

 $$ Unha fracción continua teito xeneralizada ($fctx$), $\lceil \begin{array}{ccccc}-& a_1& a_2& a_3& \dots \\ b_0& b_1& b_2& b_3& \dots \end{array}\rceil =b_0-\frac{a_1}{b_1-\frac{a_2}{b_2-\frac{a_3}{b_3-\ddots }}}$, é unha fracción continua teito onde os numeradores poden ser distintos de 1, e ten converxentes con fraccións ${\displaystyle \frac{A_i}{B_i}}$ cuxos continuantes $A_i$ e $B_i$ (numeradores e denominadores) satisfán unha recorrencia de resta da forma:

$A_i=b_i{A}_{i-1}-a_i{A}_{i-2};A_0=b_0;A_{-1}=1$.

$B_i=b_i{B}_{i-1}-a_i{B}_{i-2};B_0=1;B_{-1}=0$.

Escribiremos unha $fctx$ como unha enumeración dos seus coeficientes entre os símbolos da función teito, $\lceil \begin{array}{ccccc}-& a_1& a_2& a_3& \dots \\ b_0& b_1& b_2& b_3& \dots \end{array}\rceil$.

Para transformar unha $fctx$ noutra equivalente pode verse que unha operación sobre $a_i$ ou $b_i$ afecta aos coeficientes $a_i$, $b_i$ e $a_{i+1}$.

(Pódese consultar fracción continua xeneralizada )

Agora co algoritmo da suma por pares podemos transformar calquera serie nunha fracción continua mediante algunha transformación simple, aínda que de escrita engorrosa:

$S=\sum _{i=0}^{\mathrm{\infty }}\frac{1}{u_i}=\frac{1}{u_0}+\frac{1}{u_1}+\frac{1}{u_2}+\frac{1}{u_3}+\cdots =\frac{1}{u_0}+\frac{1}{u_0\frac{u_1}{u_0}}+\frac{1}{\frac{u_1}{u_0}{u}_2\frac{u_0}{u_1}}+\frac{1}{\frac{u_2{u}_0}{u_1}{u}_3\frac{u_1}{u_2{u}_0}}+\cdots$

E por tanto aplicando o algoritmo por pares (ver Relación entre series infinitas, fraccións continuas teito e constantes. Aplicacións (Parte I) ) temos

$S^{-1}=\lceil \begin{array}{ccccc}-& 1& 1& 1& \dots \\ u_0& \frac{\frac{u_1}{u_0}+1}{u_0}& \frac{u_0+\frac{u_2{u}_0}{u_1}}{\frac{u_1}{u_0}}& \frac{\frac{u_1}{u_0}+\frac{u_3{u}_1}{u_2{u}_0}}{\frac{u_2{u}_0}{u_1}}& \dots \end{array}\rceil =\lceil \begin{array}{ccccc}-& u_0^2& u_1^2& u_2^2& \dots \\ u_0& u_1+u_0& u_2+u_1& u_3+u_2& \dots \end{array}\rceil$

E esta fracción continua xa foi descuberta por Euler, subpoño que por outro camiño.

Como exemplo podemos ver $\zeta (2{)}^{-1}={\displaystyle \frac{6}{{\pi }^2}}=\lceil \begin{array}{ccccc}-& 1& 2^4& 3^4& \dots \\ 1& 2^2+1^2& 3^2+2^2& 4^2+3^2& \dots \end{array}\rceil =\lceil \begin{array}{ccccc}-& 1& 2^4& 3^4& \dots \\ 1& 5& 13& 25& \dots \end{array}\rceil$

Así temos os converxentes $A_i/B_i$

$a_i$			$1^4$	$2^4$	$3^4$	$\cdots$
$b_i$		1	5	13	25	$\cdots$
$A_i$	1	1	4	36	576	$\cdots$	$(n!{)}^2$
$B_i$	0	1	5	49	820	$\cdots$	secuencia A001819 na OEIS

Se sumamos ${\displaystyle \frac{1}{1^2}}+{\displaystyle \frac{1}{2^2}}+{\displaystyle \frac{1}{3^2}}+{\displaystyle \frac{1}{4^2}}$ do xeito tradicional vemos que dá ${\displaystyle \frac{205}{144}}$ e temos que ${\displaystyle \frac{820}{576}}={\displaystyle \frac{205}{144}}$, así que simplemente estamos a transformar unha suma de fraccións en dúas sumas de recorrencias.

Se procuramos as fórmulas do numerador e do denominador dos converxentes temos para o numerador $(n!{)}^2$, e para o denominador a fórmula da OEIS $a_n=s(n+1,2{)}^2-2s(n+1,1)s(n+1,3)$, onde $s(n,k)$ son os números de Stirling do primeiro tipo.

Se calculamos $\zeta (3)$ podemos ver que os numeradores son $(n!{)}^3$ e que os denominadores son secuencia A066989 na OEIS que podemos comprobar que coinciden con $a_n=s(n+1,2{)}^3-3s(n+1,1)s(n+1,2)s(n+1,3)+3s(n+1,1{)}^{2}s(n+1,4)$ (ver Stirling numbers of the first kind ).

Isto parece indicar que $\zeta (s)$ pode expresarse como o límite de $(n!{)}^s$ partido por unha pequena fórmula dos números de Stirling. Apunto este tema para investigar e se dou atopado algunha cousiña interesante farei outra entrada. De momento anoto meter a fórmula cos números de Stirling na A066989 da OEIS.

Series de potencias

Imos ver un exemplo con unha serie de Maclaurin ( Serie de Taylor):

$\ln (1+x)=\sum _{i=1}^{\mathrm{\infty }}{\displaystyle \frac{(-1{)}^{n+1}}{n}}{x}^n={\displaystyle \frac{x}{1}}-{\displaystyle \frac{x^2}{2}}+{\displaystyle \frac{x^3}{3}}-{\displaystyle \frac{x^4}{4}}+\cdots$ e así para $x={\displaystyle \frac{1}{2}},\ln 1.5\approx 0.40={\displaystyle \frac{77}{192}}={\displaystyle \frac{1}{2}}-{\displaystyle \frac{1}{8}}+{\displaystyle \frac{1}{24}}-{\displaystyle \frac{1}{64}}+\cdots$

Calculamos os converxentes $A_i/B_i$

$a_i$			$2^2=4$	$8^2=64$	${24}^2=576$	$\cdots$
$b_i$		2	-8+2=-6	24-8= 16	-64 + 24= -40	$\cdots$
$A_i$	1	2	-16	-384	24576	$\cdots$
$B_i$	0	1	-6	-160	9856	$\cdots$

Non sae un cálculo moi eficiente pois saen cifras moi grandes para unha fracción equivalente ${\displaystyle \frac{24576}{9856}}={\displaystyle \frac{192}{77}}$.

Expansión de Engel

A expansión de Engel dun número real positivo $x$ é a única secuencia non decrecente de números enteiros positivos $(a_0,a_1,a_2,a_3,\dots )$ tal que $x=\frac{1}{a_0}+\frac{1}{a_0{a}_1}+\frac{1}{a_0{a}_1{a}_2}+\cdots$

Por exemplo, o número $e$ ten unha expansión de Engel $1,1,2,3,4,5,6,7,8,\dots$ correspondente á serie infinita $e=\frac{1}{1}+\frac{1}{1}+\frac{1}{1\cdot 2}+\frac{1}{1\cdot 2\cdot 3}+\frac{1}{1\cdot 2\cdot 3\cdot 4}+\cdots$ (ver Expansión de Engel)

O cálculo da expansión dun número $x$ sería da forma: $u_1=x,a_k=\lceil \frac{1}{u_k}\rceil$ e iterar $u_{k+1}=u_k{a}_k-1$ onde $\lceil r\rceil$ é a función teito (o número enteiro máis pequeno maior ou igual a $r$).

Con esa expansión temos na suma por pares $p_i=\{a_0,a_1,a_0{a}_2,a_1{a}_3,a_0{a}_2{a}_4,a_1{a}_3{a}_4,\dots \}$ e os coeficientes da $fct$ simple $c_i=\{a_0,{\displaystyle \frac{a_0+1}{a_0}},{\displaystyle \frac{a_0(a_2+1)}{a_1}},{\displaystyle \frac{a_1(a_3+1)}{a_0{a}_2}},{\displaystyle \frac{a_0{a}_2(a_4+1)}{a_1{a}_3}},{\displaystyle \frac{a_1{a}_3(a_5+1)}{a_0{a}_2{a}_4}},\dots \}$

Se pasamos a unha $fctx$ temos: $S^{-1}=\lceil \begin{array}{ccccccc}-& a_0& a_0{a}_1& a_0{a}_1{a}_2& & a_0{a}_1{a}_2{a}_3& \dots \\ a_0& a_1+1& a_0(a_2+1)& a_1(a_3+1)& a_0{a}_2(a_4+1)& \dots \end{array}\rceil =$

$\lceil \begin{array}{cccccc}-& a_0& a_1& a_2& a_3& \dots \\ a_0& a_1+1& a_2+1& a_3+1& a_4+1& \dots \end{array}\rceil$

Un exemplo para a expansión de Engel do número $e$ vista anteriormente:

Calculamos os converxentes $A_i/B_i$

$a_i$			$1$	$1$	$2$	$3$	$4$	$5$	$\cdots$
$b_i$		1	2	3	4	5	6	7	$\cdots$
$A_i$	1	1	1	2	6	24	120	$\cdots$	n!
$B_i$	0	1	2	5	16	65	326	$\cdots$	secuencia A00522 na OEIS

así temos que ${\displaystyle \frac{326}{120}}=2.71$

e como curiosidade os denominadores forman a recorrencia $B_i=n{B}_{i-1}+1$ que se a metemos en Wolframalpha ( Wolframalpha ) devolve como solución $B_n=e\mathrm{\Gamma }(n+1)$ que ten sentido no límite pois ${\displaystyle \frac{B_n}{A_n}}={\displaystyle \frac{e\mathrm{\Gamma }(n+1)}{n!}}=e$.

Series hiperxeométricas

A función hiperxeométrica está definida para $|z|<1$ pola serie de potencias ${}_2{F}_1(a,b;c;z)=\sum _{n=0}^{\mathrm{\infty }}{\displaystyle \frac{(a{)}_n(b{)}_n}{(c{)}_n}}{\displaystyle \frac{z^n}{n!}}=1+{\displaystyle \frac{ab}{c}}\frac{z}{1!}+{\displaystyle \frac{a(a+1)b(b+1)}{c(c+1)}}{\displaystyle \frac{z^2}{2!}}+\cdots .$

Aquí $(q{)}_n$ é o Factorial ascendente (símbolo de Pochhammer ascendente), que se define por: $(q{)}_n=\{\begin{array}{ll}1& n=0\\ q(q+1)\cdots (q+n-1)& n>0\end{array}$ (ver Función hiperxeométrica )

Como temos termos con produtos consecutivos é doado aplicar a suma por pares, de feito aplicando o mesmo criterio da expansión de Engel temos $a_0=1,a_1={\displaystyle \frac{c}{abz}},a_2={\displaystyle \frac{2(c+1)}{(a+1)(b+1)z}},a_3={\displaystyle \frac{3(c+2)}{(a+2)(b+2)z}},\dots$ e por tanto a $fctx$:

$\lceil \begin{array}{cccccc}-& 1& \frac{c}{abz}& \frac{2(c+1)}{(a+1)(b+1)z}& \frac{3(c+2)}{(a+2)(b+2)z}& \dots \\ 1& \frac{c}{abz}+1& \frac{2(c+1)}{(a+1)(b+1)z}+1& \frac{3(c+2)}{(a+2)(b+2)z}+1& \frac{4(c+3)}{(a+3)(b+3)z}+1& \dots \end{array}\rceil$

Podemos ver como exemplo ${}_2{F}_1(1,1;2;-z=-1)={\displaystyle \frac{\ln (1+z)}{z}}\text{ para }z=1,\ln (2)$.

$\lceil \begin{array}{cccccc}-& 1& -2& -\frac{3}{2}& -\frac{4}{3}& \dots \\ 1& -1& -\frac{1}{2}& -\frac{1}{3}& -\frac{1}{4}& \dots \end{array}\rceil =\lceil \begin{array}{ccccccc}-& 1& -2^2& -3^2& -4^2& -5^2& \dots \\ 1& -1& -1& -1& -1& -1& \dots \end{array}\rceil$

Lembrando que para simplificar termos están afectados $a_i,b_i,a_{i+1}$.

E agora calculamos os converxentes

$a_i$			$1$	$-2^2$	$-3^2$	$-4^2$	$-5^2$	$-6^2$	$\cdots$
$b_i$		1	-1	-1	-1	-1	-1	-1	$\cdots$
$A_i$	1	1	-2	6	-24	120	-720	$\cdots$	n!
$B_i$	0	1	-1	5	-14	94	-444	$\cdots$	secuencia A00522 na OEIS

no quinto termo temos ${\displaystyle \frac{-444}{-720}}=0.61$ unha converxencia lenta cara a $\ln (2)\approx 0.69$.

Series hiperxeométricas e fracción continua de Gauss

Un resultado relacionado co Teorema da suma por pares para as $fct$ (ver Relación entre series infinitas, fraccións continuas teito e constantes. Aplicacións (Parte I)) é a fracción continua de Gauss que estabelece unha fracción continua para a división de dúas series hiperxeométricas.( ver Gauss's continued fraction))

Aquí hai que mencionar que as funcións hiperxeométricas xeneralízanse para calquera número de parámetros e así por exemplo a función ${}_0{F}_1(c;z)$ tería só un parámetro no denominador "c" e non tería os dous do numerador (nen "a" nen "b") o número á esquerda embaixo na $F$ serían os parámetros de factorial ascendente do numerador e o de embaixo na dereita serían os do denominador.

Como un exemplo da fracción continua de Gauss podemos ver o caso típico entre dúas de tipo ${}_2{F}_1(a,b;c;z)$:

${\displaystyle \frac{{}_2{F}_1(a+1,b;c+1;z)}{{}_2{F}_1(a+1,b;c+1;z)}}=$ $[\begin{array}{cccccc}+& \frac{(a-c)b}{c(c+1)}z& \frac{(b-c-1)(a+1)}{(c+1)(c+2)}z)& \frac{(a-c-1)(b+1)}{(c+2)(c+3)}z& \frac{(b-c-2)(a+2)}{(c+3)(c+4)}z& \dots \\ 1& 1& 1& 1& \dots \end{array}{]}^{-1}$

Apuntamos que esta fracción continua xeneralizada é a ordinaria, ten o signo máis entre as súas fraccións (non é teito). E tamén que o resultado é unha recíproca (elevado a $-1$). (en Mathworld Mathworld Gauss's continued fraction dan a solución con recorrencia negativa, isto é, como fracción continua teito)

Para finalizar unha integral

A función erro definida como integral e con solución como función hiperxeométrica sería:

$\mathrm{erf}(\mathrm{z})={\displaystyle \frac{2}{\sqrt{\pi }}}{\displaystyle {\int }_0^z{e}^{-t^2}dt={\displaystyle \frac{2}{\sqrt{\pi }}}M({\displaystyle \frac{1}{2}},{\displaystyle \frac{3}{2}},-z^2)}$

onde $M({\displaystyle \frac{1}{2}},{\displaystyle \frac{3}{2}},-z^2)$ é a función hiperxeométrica confluente , que é igual a unha función ${}_1{F}_1$ que só ten un parámetro no numerador e outro no denominador, neste caso ${}_1{F}_1({\displaystyle \frac{1}{2}},{\displaystyle \frac{3}{2}},-z^2)$.

Coa fracción continua dada pola suma por pares temos $a_0=1,a_1=\frac{3}{-z^2},a_2=\frac{2\cdot 5}{-3z^2},a_3=\frac{3\cdot 7}{-5z^2},\dots$ e por tanto:

${\displaystyle {\int }_0^z{e}^{-t^2}dt=\lceil \begin{array}{ccccccc}-& 1& \frac{3}{-z^2}& \frac{2\cdot 5}{-3z^2}& \frac{3\cdot 7}{-5z^2}& \frac{4\cdot 9}{-7z^2}\dots & \\ 1& \frac{3-z^2}{-z^2}& \frac{2\cdot 5-3z^2}{-3z^2}& \frac{3\cdot 7-5z^2}{-5z^2}& \frac{4\cdot 9-7z^2}{-7z^2}& \dots \end{array}{\rceil }^{-1}=}$

$\lceil \begin{array}{ccccccc}-& -z^2& -3^2{z}^2& -2\cdot 5^2{z}^2& -3\cdot 7^2{z}^2& -4\cdot 9^2{z}^2& \dots \\ 1& 3-z^2& 2\cdot 5-3z^2& 3\cdot 7-5z^2& 4\cdot 9-7z^2& 5\cdot 11-9z^2& \dots \end{array}{\rceil }^{-1}$.

Onde a segunda expresión da $fctx$ é máis simple pero dá números máis grandes nos valores dos converxentes.

Un exemplo numérico por exemplo para $z=1$ temos:

$a_i$			$-1$	$-9$	$-50$	$-147$	$\cdots$
$b_i$		1	2	7	16	29	$\cdots$
$A_i$	1	1	3	30	630	22680	$\cdots$	${\displaystyle \frac{(2n+1)!}{2^n}}$ (A007019 na OEIS)
$B_i$	0	1	2	23	468	16953	$\cdots$

${\displaystyle {\int }_0^1{e}^{-t^2}\approx {\displaystyle \frac{16953}{22680}}\approx 0.747486}$.

Criptografía e maxia no Losada

Algún día tería que relatar as miñas desventuras no CAP (Curso de Adaptación Pedagóxiga), un curso que xogaba aproximadamente o mesmo papel que o Máster de Profesorado actual. Só comentarei que, cando me faltaba só unha sesión para rematalo, abandoneino, farto.  Efectivamente, estaba farto de ver como quen presumiblemente tiña que dar directrices sobre orientacións didácticas actuaba como un terrorista pedagóxico. Recordo unha materia levada por dous profesores, un home gordo e unha muller fraca. Impartían clase xuntos. Pasaban todo o tempo discutindo. Iso podería estar ben se fose algo pensado e preparado. Non era o caso.  Nunha ocasión pasaran toda a sesión dándolle voltas a como tratar aos rapaces zurdos. Se conviña, ou non, forzalos a escribir coa man dereita. Non era esta un tema que houbese que tratar no CAP, só foi unha ocorrencia máis desa parella infame de profesores. Desde aquela quedoume a impresión que unha clase levada en parella tiña que ser necesariamente un fracaso. Non é así. Isto demostráronolo Nicanor Alonso e Miguel Mirás o pasado venres 16/05/2025 na charla que viñeron impartir ao IES Antón Losada Diéguez ao alumnado de 1º de Bacharelato. O segredo do éxito dunha clase en tándem? O mesmo que o dunha clase impartida por unha persoa soa: traballo e preparación. 

O título da charla era "Historias e segredos da criptografía". Trataron temas como o da escritura xeroglífica, a reixa de Cardano, os acrósticos, a escítala espartana, o cifrado César ou o máis sofisticado de Vigenére,  sempre solicitando a participación e complidade do alumnado. Nicanor e Miguel repartiron unha roda como a da imaxe, que nos permitiu encriptar unha mensaxe seguindo as directrices dos dous últimos sistemas de cifrado. 

Examinaron moitos máis tópicos e sempre dunha forma clara e coordinada. Claro que, no canto de ser explicados en parella, tal e como o fixeron eles, case todos podían ter sido tratados por un só conferenciante. Comento isto porque un dos capítulos necesitaba de dúas persoas para poder desenvolvelo. A min foi o que máis me sorprendeu e agradou. Trátase do truco das 5 cartas de Cheney, asunto do que, por certo, xa se ocupara no seu día Jota nesta entrada, O mellor truco de cartas. O enunciado promete. Vexamos como se desenvolveu.

As cinco cartas de Cheney

Un dos dous conferenciantes marchou da sala; chamémoslle  mago. O outro, chamémoslle axudante,  pediu a un voluntario que escollera cinco cartas dunha baralla francesa completa (52 cartas, 13 de cada un dos paus, a saber: corazóns ♡ , diamantes ♢, picas ♠ e trevos ♣). Entón o axudante colocou catro desas cartas sobre unha mesa e deixou a quinta ao final, virada cara abaixo.

Cando volveu o mago e veu esas cartas sobre a mesa, concentrouse un momento e adiviñou cal era a carta que estaba boca abaixo.

Estaba claro que elaboraran un código para identificar as cartas pois diso trataba a conferencia. Pero teñamos presente que non poden saber previamente cales son as cartas que se van escoller polo que o código debería estar montado sobre a ordenación das cartas. Está claro que podemos establecer unha orde entre todas elas. En primeiro lugar, os números (do 1 ao 13) axudan moito. E que pasa se dúas cartas teñen o mesmo valor numérico? Daquela basta con que o mago e o seu axudante establezan unha orde dos paus. Podería ser, por exemplo, a orde do abecedario pola primeira letra: corazóns ♡ < diamantes ♢< picas ♠ < trevos ♣. Con todo, hai un problema, as $4$ cartas que quedan visibles só poden ordenarse de $4!=24$ formas distintas. 

Para salvar esta dificultade hai que aproveitar todas as vantaxes que nos dá o desenvolvemento do truco. Teñamos presente que é o axudante quen escolle a carta que se coloca boca abaixo. Polo principio do pombal, dadas $5$ cartas, é seguro que vai haber polo menos dúas do mesmo pau. Isto permite que o axudante escolla dúas cartas do mesmo pau e coloque unha cara abaixo e a outra pode colocala na primeira posición. No noso exemplo a primeira carta era o rei de trevos, velaí que a carta a adiviñar será tamén un trevo. Agora quédannos outras tres cartas visibles que nos deben permitir identificar o número da carta oculta. Outra vez, se ordenamos esas tres cartas termos un total de só $3!=6$ posibilidades e nós necesitamos 13. Aquí é onde entra en xogo a aritmética modular. 

Facemos unha identificación do valor da carta cos números das congruencias de ${\mathbb{Z}}_{13}$. A diferenza entre dous destes valores nunca é maior que $6$. As cartas que escolleu o axudante eran a $J$ e o $2$ de trevos. A súa diferenza é de $4$ unidades. Ocultando o $2$ só lle ten que dicir ao seu compañeiro que debe sumarlle $4$ unidades á $J$. En aritmética modular $11+4\equiv 2(mód13)$. O código utilizado para indicar o número a sumar é o que explicamos de seguido. Vou identificar o $1$ co valor máis baixo das tres cartas, o $2$ co intermedio e o $3$ co maior. Daquela establezo a seguinte relación entre as $6$ ordenacións e o $6$ números que debo sumar (módulo 13) ao valor da primeira carta:

$$\left(\begin{array}{cc}1,2,3& ⟶1\\ 1,3,2& ⟶2\\ 2,1,3& ⟶3\\ 2,3,1& ⟶4\\ 3,1,2& ⟶5\\ 3,2,1& ⟶6\end{array}\right)$$

Como as tres cartas centrais son: $J$♢, $3$♠, $5$♠ vemos que a orde das cartas é: maior,  menor, intermedia que identificamos coa permutación $3,2,1$, de aí que o número a sumar é o $4$. Polo tanto o mago adiviña a carta oculta:

Principio do pombal, combinatoria e aritmética modular, todo dentro dun truco de maxia. 

Charlas científico-divulgativas

A Universidade de Vigo ofrece cada ano charlas científico-divulgativas. No seu folleto divulgativo acharemos epígrafes como os de "Ciencias da natureza", "Física e Química" ou "Economía". Aparentemente non se oferta ningunha charla de "Matemáticas". Eu aconsellaría aos centros de ensino de Secundaria buscar nese folleto os nomes de Nicanor Alonso e Miguel A. Mirás e concertar con eles unha actividade.