Subsequence Sums in Permutations

Sintesi Tecnica: Somme di Sottosequenze nelle Permutazioni

Enunciato del Problema
Questo lavoro indaga l'esistenza di specifiche sottosequenze aritmetiche all'interno di permutazioni dell'insieme $\{1, 2, \dots, n\}$. Sebbene la teoria di Ramsey aritmetica classica (ad esempio, il teorema di van der Waerden) garantisca progressioni aritmetiche monocromatiche in insiemi colorati sufficientemente grandi, Entringer e Jackson (1973) hanno dimostrato che le permutazioni possono evitare progressioni aritmetiche monotone di 3 termini (3-AP). Gli autori chiedono se altre proprietà aritmetiche, specificamente le sottosequenze "additive", siano inevitabili nelle permutazioni di grandi dimensioni.

Una sequenza di interi positivi $(a_1, a_2, \dots, a_k)$ è definita $\ell$-additiva se la somma dei suoi termini soddisfa $\sum_{i=1}^k a_i = \ell a_1$ oppure $\sum_{i=1}^k a_i = \ell a_k$. Il focus principale è sulle sottosequenze 2-additive (dove la somma è uguale al doppio del primo o dell'ultimo termine) e sulle loro varianti monotone. Il lavoro affronta due domande principali:

1. Per una lunghezza fissa $k \ge 3$, esiste un $n$ tale che ogni permutazione di $\{1, \dots, n\}$ contenga una sottosequenza 2-additiva di lunghezza $k$?
2. Quali sono le soglie e i limiti precisi per l'esistenza di tali sottosequenze, in particolare quando ristrette a sequenze monotone?

Metodologia
Gli autori impiegano una combinazione di argomenti combinatori, analisi dei casi e tecniche dalla teoria di Ramsey aritmetica.

• Costruzione Combinatoria e Contraddizione: Le dimostrazioni fondamentali per l'esistenza (Teoremi 1.1 e 1.3) si basano sulla costruzione di specifici sottoinsiemi di permutazioni e sull'uso della dimostrazione per contraddizione. Analizzando le posizioni relative degli elementi (usando $L_p(s)$ e $R_p(s)$ per denotare gli elementi a sinistra e a destra di $s$ in una permutazione $p$), gli autori dimostrano che evitare una sottosequenza 2-additiva forza una contraddizione strutturale nel layout della permutazione.
• Tecniche di Limitazione: Per stabilire i limiti superiori per il più piccolo $n$ (denotato $f(k, 2)$), gli autori definiscono un insieme di somme "pericolose" derivate dai primi $2k-1$ elementi di una permutazione. Utilizzano il minimo comune multiplo (mcm) di queste somme per determinare una soglia $N_k$ oltre la quale una sottosequenza 2-additiva è forzata.
• Limiti Inferiori e Controesempi: I limiti inferiori sono stabiliti costruendo esplicitamente permutazioni di dimensione $n-1$ che mancano delle sottosequenze desiderate.
• Analisi Asintotica: Il lavoro utilizza il Teorema dei Numeri Primi (tramite i risultati di Rosser) per derivare limiti inferiori sul numero di tali sottosequenze in permutazioni di grandi dimensioni.
• Argomenti di Trasformazione: Per estendere i risultati ai prodotti e alle somme inverse, gli autori usano trasformazioni standard che mappano proprietà additive in $\{1, \dots, n\}$ su proprietà moltiplicative in $\{2^1, \dots, 2^n\}$ e proprietà additivo-inverse in $\{L_n/1, \dots, L_n/n\}$ (dove $L_n$ è il mcm di $1$ fino a $n$).

Contributi e Risultati Chiave

1. Esistenza di Sottosequenze 2-Additive (Teorema 1.1):
   Per ogni $k \ge 3$ fissato, se $n$ è sufficientemente grande, ogni permutazione di $\{1, \dots, n\}$ contiene una sottosequenza 2-additiva di lunghezza $k$.

   • Limiti: Il lavoro fornisce limiti polinomiali per il più piccolo tale $n$, denotato $f(k, 2)$.
     • Limite inferiore: $f(k, 2) \ge (k-1)(3k-4)/2$.
     • Limite superiore: $f(k, 2) \le 9(k-2)(k^2-k)^2/4$.
   • Valore Esatto per $k=3$: Gli autori dimostrano che $f(3, 2) = 5$. Ogni permutazione di $\{1, \dots, 5\}$ contiene una sottosequenza 2-additiva di lunghezza 3, mentre un controesempio esiste per $n=4$.

2. Sottosequenze 2-Additive Monotone (Teorema 1.3):
   Il lavoro affronta la condizione più rigorosa in cui la sottosequenza deve essere monotona.

   • Risultato: Se $n \ge 18$, ogni permutazione di $\{1, \dots, n\}$ contiene una sottosequenza 2-additiva monotona di lunghezza 3.
   • Ottimalità: Il valore 18 è ottimale; viene costruita una specifica permutazione di $\{1, \dots, 17\}$ che evita tali sottosequenze.
   • Domanda Aperta: Rimane sconosciuto se ciò valga per sottosequenze 2-additive monotone di lunghezza $k \ge 4$.

3. Sottosequenze $\ell$-Additive Generali:

   • Se $k = \ell$, la permutazione identità $(1, 2, \dots, n)$ non contiene alcuna sottosequenza $\ell$-additiva di lunghezza $k$.
   • Il lavoro risolve due casi misti specifici:
     • $f(4, 3) = 8$ (Ogni permutazione di 8 elementi ha una sottosequenza 3-additiva di lunghezza 4).
     • $f(3, 4) = 13$ (Ogni permutazione di 13 elementi ha una sottosequenza 4-additiva di lunghezza 3).
   • Il caso generale per $k \neq \ell$ con $k, \ell \ge 4$ è lasciato come domanda aperta.

4. Conteggio delle Sottosequenze:
   Gli autori forniscono limiti sul numero minimo di sottosequenze $\ell$-additive di lunghezza $k$ in qualsiasi permutazione di dimensione $n$:

   • Limite Superiore: $O(n^{k-1})$.
   • Limite Inferiore: $\Omega(n / \log n)$ (assumendo che $f(k, \ell)$ esista), derivato utilizzando argomenti sulla distribuzione dei numeri primi.
   • Limiti specifici per sottosequenze 2-additive monotone di lunghezza 3 sono dati come $n/[18(\log n - \log 18 + 2)] - 6 \le G(3, 2, n) \le \frac{1}{18}n^2 + \frac{7}{6}n$.

5. Estensioni a Prodotti e Somme Inverse:
   Utilizzando trasformazioni della teoria di Ramsey aritmetica, il lavoro estende i risultati additivi a:

   • Moltiplicativo: Ogni permutazione sufficientemente grande ha una sottosequenza in cui il prodotto è il quadrato del primo o dell'ultimo termine (2-moltiplicativa).
   • Additivo-Inverso: Ogni permutazione sufficientemente grande ha una sottosequenza in cui la somma dei reciproci è il doppio del reciproco del primo o dell'ultimo termine.
   • Il lavoro nota che per sottosequenze 2-moltiplicative monotone di lunghezza 3, la soglia è al massimo 32 (ed esattamente 32, poiché un controesempio esiste per $n=31$).

Significato e Affermazioni
Il lavoro afferma di stabilire i primi risultati di tipo Schur-Rado specificamente per le permutazioni, dimostrando che mentre le permutazioni possono evitare progressioni aritmetiche monotone (3-AP), non possono evitare sottosequenze 2-additive di lunghezza arbitraria. Il lavoro fornisce i primi limiti polinomiali per l'esistenza di queste strutture e determina soglie esatte per casi piccoli ($k=3$).

Gli autori inquadrano modestamente il loro contributo come una base per ulteriori studi. Evidenziano che il caso generale per $k \neq \ell$ rimane aperto e che il comportamento delle sottosequenze 2-additive monotone per lunghezze $k > 3$ è sconosciuto. Il lavoro posiziona queste scoperte come un passo verso la comprensione dell'interazione tra la struttura delle permutazioni e le proprietà aritmetiche, suggerendo direzioni future nelle somme pesate di sottosequenze e nel raffinamento delle soglie per varianti moltiplicative e additivo-inverse.