Ogni funzione simmetrica può essere scritta come una funzione di una somma?

Aug 23 2020

Sto cercando un semplice controesempio a un "teorema" sulle funzioni simmetriche rivendicato in un articolo pubblicato. L'affermazione afferma, tra molte altre cose, che ci sono funzioni$\sigma$e$\rho$tale che, per tutti$x,y\in\mathbb R$,$$ \max(x,y) = \sigma(\rho(x) + \rho(y)). $$Il documento non specifica il dominio di$\sigma$, che è, ovviamente, anche la gamma di$\rho$. Indicherò questo sconosciuto con$G$. E supponiamo che$G$è un tipo ben noto di oggetto matematico, in cui l'addizione è convenzionalmente definita, ad esempio un semigruppo abeliano.

Può$\sigma$e$\rho$essere trovato, se$G$è un (semi)gruppo abeliano? Cosa succede se$X$è un insieme e$G = \mathbb R^X$è l'insieme delle funzioni da$X$a$\mathbb R$?

In realtà, dal momento che i numeri reali non possono essere gestiti da una macchina di Turing, e la rivista in cui compare l'articolo è dedicata all'informatica, preferirei una discussione in cui i reali fossero sostituiti in tutto il passaggio precedente dagli interi. Mi aspetto che l'affermazione sia errata per qualsiasi contesto ragionevole (non finito).

Se i reali sono sostituiti da un intervallo chiuso finito di numeri reali, qualsiasi funzione simmetrica continua può essere approssimata da un polinomio simmetrico, e quindi si possono usare le identità di Newton per ottenere un risultato approssimativo. Forse questo è ciò che l'autore dell'articolo in questione pensava, ma non affermava.

Risposte

6 QiZhu Aug 23 2020 at 18:05

Rispondo alla tua domanda per$\mathbb{R} \to \mathbb{R}$.

Permettere$r(x,y) = p(x) + p(y)$. La tua domanda si riduce al fatto che esista$p$tale che$r$è iniettiva fino alla simmetria.

Da$\mathbb{R}$ha una dimensione innumerevole$\mathbb{Q}$, esiste per ciascuno$x \in \mathbb{R}$alcuni$t_x \in \mathbb{R}$tale che il set$\{t_x \}_x$è linearmente indipendente. Impostare$p(x) = t_x$, Così$r$è iniettiva e quindi esiste a$\sigma$come desiderato.

(Questo usa l'assioma della scelta.)

Modifica: immagino che utilizzi anche l'ipotesi del continuum. Immagino che dovrebbe esserci una prova per evitare alcuni di questi?

Modifica 2: come sottolineato nei commenti, CH non è necessario.

5 user21820 Aug 23 2020 at 18:28

Per numeri interi: Let$ρ(x) = 2^x$per ogni numero intero$x$. Poi dato$ρ(x)+ρ(y)$puoi guardare la forma binaria per determinare$x,y$e quindi il loro massimo.

1 GregMartin Aug 24 2020 at 04:53

Una versione più concreta dell'idea dalla risposta di user21820 , per la situazione in cui il dominio del discorso sono i numeri interi:

Definire$\rho(x) = 4^x$, e definire$\sigma(t) = \lfloor \log_4 t\rfloor$, dove$\log_4$è il logaritmo in base 4.

1 user21820 Aug 24 2020 at 14:00

Per davvero: Let$d(x,k) = \lfloor x·2^k \rfloor$per ogni$x∈ℝ$e naturale$k$. Permettere$ρ(x) = \{ ⟨k,2^{d(x,k)}⟩ : k∈ℕ \}$per ogni$x∈ℝ$. Quindi$ρ(x)$rappresenta una sequenza univoca da$ℕ$per ciascuno$x∈ℝ$. Definisci addizione su sequenze da$ℕ$essere un'addizione puntuale. Quindi per qualsiasi$x,y∈ℝ$, possiamo determinare$z = \max(x,y)$da$ρ(x)+ρ(y)$come segue.

Possiamo facilmente ottenere$S(k) = \{d(x,k),d(y,k)\}$per ciascuno$k∈ℕ$. E$d(z,k) = \max(d(x,k),d(y,k))$per ogni$k∈ℕ$. Per capire perché, nota che: (1) per qualsiasi$m∈ℕ$abbiamo che se$d(x,m) > d(y,m)$poi$d(x,k) > d(y,k)$per ogni$k∈ℕ_{>m}$anche; (2) se$x > y $poi$d(x,m) > d(y,m)$per alcuni$m∈ℕ$. Quindi possiamo ottenere$z$poiché è univocamente determinato da$\{ ⟨k,d(z,k)⟩ : k∈ℕ \}$.

Questo è completamente costruttivo (ciascuna delle funzioni desiderate è calcolabile dove ogni input o output$x$è dato come un oracolo per$d(x,•)$).

1 MishaLavrov Aug 24 2020 at 07:24

La soluzione per numeri interi si generalizza a una soluzione costruttiva per numeri reali, come segue.

Definire$\rho$, per prima cosa applica una mappa costruttiva rigorosamente crescente da ridurre al caso in cui tutti i nostri numeri si trovano tra$0$e$1$. Una di queste trasformazioni è$x' = \frac12 + \frac1\pi \arctan x$.

Quindi, dato un valore$x' \in (0,1)$, annotare la sequenza di zeri e uno:

  • Un blocco di lunghezza$3$in cui la$\lceil 2x'\rceil^{\text{th}}$po' è un$1$, e gli altri lo sono$0$.
  • Un blocco di lunghezza$4$in cui la$\lceil 3x'\rceil^{\text{th}}$po' è un$1$, e gli altri lo sono$0$.
  • Un blocco di lunghezza$5$in cui la$\lceil 4x'\rceil^{\text{th}}$po' è un$1$, e gli altri lo sono$0$.
  • E così via. In generale, per ciascuno$n$, un blocco di lunghezza$n+1$in cui la$\lceil nx'\rceil^{\text{th}}$po' è un$1$, e gli altri lo sono$0$. Si noti che l'ultimo bit in ogni blocco è$0$.

Allora prendi$\rho(x) \in (0,1)$essere il numero la cui espansione binaria è questa sequenza.

Dato$\rho(x) + \rho(y)$, possiamo trovare$\max\{x,y\}$come segue. La somma dei blocchi di lunghezza$n+1$ci dice$2^{\lceil nx'\rceil} + 2^{\lceil ny'\rceil}$, da cui possiamo dedurre$\lceil nx'\rceil$e$\lceil ny'\rceil$fino alla permutazione. Possiamo capirlo per arbitrariamente grande$n$, che ci fornisce una sequenza di approssimazioni arbitrariamente buone a$x'$e$y'$, da cui$x$e$y$può anche essere trovato.