martes, 22 de xullo de 2025

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 ber(modm), 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 m1.

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: (bb1)modm=(bmodm)(b1modm) Imos mostrar os 4 métodos co exemplo da wikipedia Modular exponentiation 413r(mod497)

Non esquezamos que se a base é maior que o módulo pódese aplicar primeiro o módulo á base, por exemplo: 50113c(mod497) implica 413c(mod497). Isto sería común para todos os métodos.

O método directo

O método directo sería obter be e calcular o seu residuo, así 413=67108864mod497=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: 4mod497=416mod497=1664mod497=64256mod497=2561024mod497=30304=120mod497=120e igualmente ata o último paso4844=1936mod497=445

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: R1(=b0) e xb=4.Paso 1) o bit 1 é 1, así que se estabelece RR44(mod497); agora xx2 (=b2)4216(mod497). Paso 2) o bit 2 é 0, polo que non recalculamos ''R''; así xx2 (=b4)162256(mod497). Paso 3) o bit 3 é 1, así que recalculamos ''R''RRx (=b5)425630(mod497); agora xx2 (=b8)2562429(mod497). Paso 4) o bit 4 é 1, así que recalculamos ''R''RRx (=b13)30429445(mod497); 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 e1 de b máis próxima ao módulo m (sería válido superiormente ou inferiormente), calcular o módulo con este resultado be1c1(modm) e calculando a división enteira dos espoñentes ee1 con e=e1d+r transformamos a expresión orixinal con cifras moito menores. Para o noso exemplo: 45=1024 e 13=25+3102430(mod497).R=30,x=3024330294(mod497).9464=601652(mod497).R=49752=445. 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: 413=226c(mod7)231(mod7) e 26=83+2(1)844(mod7). E mellor aínda, aplicando directamente Fermat: Se a é un enteiro e p é un primo que non divide a, daquela ap11(modp). (Emanuel Lazar) notes06-3.pdf Temos: 261(mod7) e 26=64+2(1)444(mod7). Imos comparar con algúns exemplos vistos na rede: fast modular exponentiation (Khan Academy) 7256c(mod13) daquela 7121(mod13) e 2564(mod12)74(mod13)(3)2(mod13)=9(mod13). Por último temos o teorema de Fermat-Euler: Se a e n son enteiros positivos coprimos daquela aϕ(n)1(modn). Teorema de Euler (Galipedia) Onde ϕ(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: 7222c(mod10) así temos 72=491(mod10) e 222=2111+0.(1)111(mod10)1(mod10)9(mod10).

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)

martes, 15 de xullo de 2025

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  AX se verifique que |A||N(A)|

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 f1,f2,...,fn e outros tantos cabaleiros c1,c2,...,cn estableceremos unha matriz A=(aij) onde aij=1 se fi e cj están dispostos a casar. No caso contrario escribiremos aij=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: (f1,c3),(f2,c4) e (f3,c2):
Esta matriz dá lugar ao seguinte grafo no que resaltamos con arestas grosas os tres matrimonios:
Se escollo as tres últimas filas {f2,f3,f4} comprobo inmediatamente que a súa veciñanza está formada por só dúas columnas {c2,c4}. 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. 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×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 |M|<|K|. 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×s con r+s>n
  • A cada subconxunto de 1rn mozas lles gustan polo menos r mozos
  • A cada subconxunto de 1sn mozos lles gustan polo  menos s mozas
Na seguinte entrada veremos máis aplicación do teorema de Hall.

martes, 8 de xullo de 2025

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 524=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 P4=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 54!+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(n1)!+n1=n!+n1 cartas [1]. Na seguinte táboa mostramos os primeiros valores.

n m=n!+n1
1 1
23
3 8
427
5124
6725

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á C8,3=(83)=56 formas posibles de escoller 3 cartas. Agora o axudante debe deixar dúas delas cara arriba nunha determinada orde. Hai un total de A8,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 C27,4=(274)=A17,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 Cm,n=(mn) posibilidades, e as ordenación de n1 cartas que faga o axudante. Este último valor contabilízase mediante os arranxos Am,n1=m(m1)...(mn+2). Se igualamos estas expresións:

Cm,n=(mn)=m!n!(mn)!=Am,n1=m!(mn+1)!

Igualando denominadores e operando:

(mn+1)!=n!(mn)! (mn+1)!(mn)!=n! mn+1=n! m=n!+n1

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  AX se verifique que |A||N(A)|

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(A) 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!+n1 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 Cm,n escollas e as Am,n1 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 n1 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 AX 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(A), deben chegar n!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 (535)=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 (1245)=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. 

martes, 1 de xullo de 2025

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

 

luns, 23 de xuño de 2025

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=107. En concordancia con isto estableceu como base para os seus logaritmos un valor moi próximo, e menor, á unidade, k=11107=11r. 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 Q1, Q2, Q3,... Qn 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

OQn=n(rt)

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=107. Sexa k a constante. A intervalos regulares de tempo t o punto estará en posicións P1,P2,P3,...,Pn... e neses puntos terá velocidades v1,v2,v3,...,vn... 

Daquela:

BPn+1BPn=vn+1vn=kBPn+1=kBPn

BPn=BPn+1+PnPn+1=BPn+1+vnt

Das igualdades anteriores dedúcese que:

BPn=kBPn+vnt (1k)BPn=vnt vn=1ktBPn

Tomando 1k=t temos que vn=BPn

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

BPn=kBPn1=k2BPn2=...=knBP0=knBA=rkn

Nótese que, como xa comentaramos, BA=r=107

Napier define o seu logaritmo, ao que chamaremos como fai Juan Havil no  libro Gamma (Pricenton 2003), NapLog, da seguinte maneira: NapLog(BPn)=OQn, isto é  NapLog[rkn]=n. Aquí é onde Napier escolle o valor infinitesimal de t; toma t=1r=1107. Se traducimos a definición de NapLog usando que r=107 e que k=1t=11107 obteremos a seguinte expresión:

NapLog[107(11107)n]=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:

N1=rkn1;n1=NapLog(rkn1)  

N2=rkn2;n2=NapLog(rkn2) 

N1N2=rrkn1kn2=rrkn1+n2

N1N2r=rkn1+n2

NapLog(N1N2r)=NapLog(rkn1+n2)=n1+n2=NapLogN1+NapLogN2


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á dydt=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=rx, verificará d(rx)dt=x polo que dxdt=x. Separando as variables: dxx=t e integrando: lnx=t+c1 con c1 unha constante. De aí que x(t)=ec1et

Chamémoslle ρ=ec1 a esta constante. Así escribiremos x(t)=ρet. Valorando esta expresión en t=0: x(0)=ρ=r. En conclusión:

x(t)=ret[2]  

De [1]  obtemos t=yr

De [2] obtemos que xr=et entón t=lnxr=log1exr

Igualando 

yr=logexr y=NapLog(x)=rln(xr)[3]

Se agora redimensionamos os valores a unha circunferencia de raio 1:   X=xr e Y=yr concluímos que yr=log1exr

Equivalentemente, que o logaritmo de Napier é unha aproximación do logaritmo en base 1e:

Y=log1eX

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(x)=NapLog[r(11r)n]=n

Está claro que tomamos x=r(11r)n. Despexemos n tomando logaritmos neperianos:

xr=(11r)n ln(xr)=ln(11r)n ln(xr)=nln(r1r) n=NapLog(x)=1ln(r1r)ln(xr)[4]

Repetimos deseguido a fórmula obtida usando ecuacións diferenciais y=NapLog(x)=rln(xr)[3]

En [3] e en [4] temos dúas fórmulas distintas para o NapLog, diferéncianse no coeficiente de ln(xr). Para comparalas calcularemos q, o cociente deses coeficientes:

q=r:1ln(r1r)=rln(r1r)=ln(r1r)r=ln(rr1)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 que se traballan na materia de Matemáticas II, en 2º de bacharelato. limr(rr1)r=eλ

Con λ=limrr(rr11)=limrr1r1=1

De aí que qlimrln(rr1)r=lne1=1

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

q=ln(rr1)r=ln(1071071)107=1,00000005000000333333358333335333333500000014285...

En conclusión, o logaritmo orixinal de Napier era case o logaritmo en base 1e

luns, 2 de xuño de 2025

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), a1a2a3b0b1b2b3=b0a1b1a2b2a3b3, é unha fracción continua teito onde os numeradores poden ser distintos de 1, e ten converxentes con fraccións AiBi cuxos continuantes Ai e Bi (numeradores e denominadores) satisfán unha recorrencia de resta da forma:

Ai=biAi1aiAi2; A0=b0; A1=1.

Bi=biBi1aiBi2; B0=1; B1=0.

Escribiremos unha fctx como unha enumeración dos seus coeficientes entre os símbolos da función teito, a1a2a3b0b1b2b3.

Para transformar unha fctx noutra equivalente pode verse que unha operación sobre ai ou bi afecta aos coeficientes ai, bi e ai+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=i=01ui=1u0+1u1+1u2+1u3+=1u0+1u0u1u0+1u1u0u2u0u1+1u2u0u1u3u1u2u0+

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

S1=111u0u1u0+1u0u0+u2u0u1u1u0u1u0+u3u1u2u0u2u0u1=u02u12u22u0u1+u0u2+u1u3+u2

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

Como exemplo podemos ver ζ(2)1=6π2=12434122+1232+2242+32=12434151325

Así temos os converxentes Ai/Bi

ai142434
bi151325
Ai11436576(n!)2
Bi01549820secuencia A001819 na OEIS

Se sumamos 112+122+132+142 do xeito tradicional vemos que dá 205144 e temos que 820576=205144, 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 an=s(n+1,2)22s(n+1,1)s(n+1,3), onde s(n,k) son os números de Stirling do primeiro tipo.

Se calculamos ζ(3) podemos ver que os numeradores son (n!)3 e que os denominadores son secuencia A066989 na OEIS que podemos comprobar que coinciden con an=s(n+1,2)33s(n+1,1)s(n+1,2)s(n+1,3)+3s(n+1,1)2s(n+1,4) (ver Stirling numbers of the first kind ).

Isto parece indicar que ζ(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)=i=1(1)n+1nxn=x1x22+x33x44+ e así para x=12,ln1.50.40=77192=1218+124164+

Calculamos os converxentes Ai/Bi

ai22=482=64242=576
bi2-8+2=-624-8= 16-64 + 24= -40
Ai12-16-38424576
Bi01-6-1609856

Non sae un cálculo moi eficiente pois saen cifras moi grandes para unha fracción equivalente 245769856=19277.

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 (a0,a1,a2,a3,) tal que x=1a0+1a0a1+1a0a1a2+

Por exemplo, o número e ten unha expansión de Engel 1,1,2,3,4,5,6,7,8, correspondente á serie infinita e=11+11+112+1123+11234+ (ver Expansión de Engel)

O cálculo da expansión dun número x sería da forma: u1=x,ak=1uk e iterar uk+1=ukak1 onde r é 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 pi={a0,a1,a0a2,a1a3,a0a2a4,a1a3a4,} e os coeficientes da fct simple ci={a0,a0+1a0,a0(a2+1)a1,a1(a3+1)a0a2,a0a2(a4+1)a1a3,a1a3(a5+1)a0a2a4,}

Se pasamos a unha fctx temos: S1=a0a0a1a0a1a2a0a1a2a3a0a1+1a0(a2+1)a1(a3+1)a0a2(a4+1)=

a0a1a2a3a0a1+1a2+1a3+1a4+1

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

Calculamos os converxentes Ai/Bi

ai112345
bi1234567
Ai1112624120n!
Bi01251665326secuencia A00522 na OEIS

así temos que 326120=2.71

e como curiosidade os denominadores forman a recorrencia Bi=nBi1+1 que se a metemos en Wolframalpha ( Wolframalpha ) devolve como solución Bn=eΓ(n+1) que ten sentido no límite pois BnAn=eΓ(n+1)n!=e.

Series hiperxeométricas

A función hiperxeométrica está definida para |z|<1 pola serie de potencias 2F1(a,b;c;z)=n=0(a)n(b)n(c)nznn!=1+abcz1!+a(a+1)b(b+1)c(c+1)z22!+.

Aquí (q)n é o Factorial ascendente (símbolo de Pochhammer ascendente), que se define por: (q)n={1n=0q(q+1)(q+n1)n>0 (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 a0=1,a1=cabz,a2=2(c+1)(a+1)(b+1)z,a3=3(c+2)(a+2)(b+2)z, e por tanto a fctx:

1cabz2(c+1)(a+1)(b+1)z3(c+2)(a+2)(b+2)z1cabz+12(c+1)(a+1)(b+1)z+13(c+2)(a+2)(b+2)z+14(c+3)(a+3)(b+3)z+1

Podemos ver como exemplo 2F1(1,1;2;z=1)=ln(1+z)z para z=1,ln(2).

12324311121314=122324252111111

Lembrando que para simplificar termos están afectados ai,bi,ai+1.

E agora calculamos os converxentes

ai12232425262
bi1-1-1-1-1-1-1
Ai11-26-24120-720n!
Bi01-15-1494-444secuencia A00522 na OEIS

no quinto termo temos 444720=0.61 unha converxencia lenta cara a ln(2)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 0F1(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 2F1(a,b;c;z):

2F1(a+1,b;c+1;z)2F1(a+1,b;c+1;z)= [+(ac)bc(c+1)z(bc1)(a+1)(c+1)(c+2)z)(ac1)(b+1)(c+2)(c+3)z(bc2)(a+2)(c+3)(c+4)z1111]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

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

erf(z)=2π0zet2dt=2πM(12,32,z2)

onde M(12,32,z2) é a función hiperxeométrica confluente , que é igual a unha función 1F1 que só ten un parámetro no numerador e outro no denominador, neste caso 1F1(12,32,z2).

Coa fracción continua dada pola suma por pares temos a0=1,a1=3z2,a2=253z2,a3=375z2, e por tanto:

0zet2dt=13z2253z2375z2497z213z2z2253z23z2375z25z2497z27z21=

z232z2252z2372z2492z213z2253z2375z2497z25119z21.

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:

ai1950147
bi1271629
Ai1133063022680(2n+1)!2n (A007019 na OEIS)
Bi0122346816953

01et216953226800.747486.

mércores, 28 de maio de 2025

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 Z13. 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+42(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:

(1,2,311,3,222,1,332,3,143,1,253,2,16)
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.