Je pense comme Christophe Chalons que chercher sur les lignes et les colonnes ne change rien au caractère polynomial.
Il a certes oublié qu'il ne fallait pas compter plusieurs fois les coeffs aux intersections mais cela ne fait que rajouter quelques tests et diminuer le nombre d'opérations.

A vu de nez, pour la calculer, j'imagine choisir un entier i entre 0 et k donnant le nombres de lignes (k-i donnant le nombre de colonnes) puis choisir les i lignes parmi n et les k-i colonnes parmi n, faire la somme des k*n (au plus) termes sur ces lignes et colonnes et comparer les résultats.
J'obtiens donc une complexité majorée par $$k n \sum_{i=0}^k C_n^i C_n^{k-i} \leq k n \sum_{i=0}^k \frac{n^i n^{k-i}}{i!(k-i)!}=\frac{2^k n^{k+1}}{(k-1)!}$$

C'est bien polynomial...
A moins que je fasse erreur quelque part.

J'ai du mal à vous suivre. Ok pour travailler sur $\mathbb{R}/\mathbb{Z}$, même en binaire si cela vous arrange. Cependant, si par hasard la suite dans $\{0,1\}^{\mathbb{N}^*}$ que vous choisissez s'avère donner un rationnel, l'orbite sera périodique à partir d'un certain rang, donc loin d'être dense.

Merci de m'éclairer.

[Corrigé selon ton indication. AD]

@Miskha: c'est pas mon idée, c'est expliqué sur wikipédia.
les entiers naturels premiers se raréfiant asymptotiquement, $(\mathbb{N}, \times)$ se compactifie en espace projectif, les polynômes deviennent des fonctions périodiques de leur degré. $z^n=e^{n log(|z|)+ n i \arg(z)}$ avec prépondérance de l'argument $\arg(z)$ sur le module $|z|$.
en coordonnées polaires planes, à l'infini, une variation d'angle déplace beaucoup plus le point courant qu'une variation de rayon.

Considérons maintenant une fonction $F$ élément d'une famille française de fonctions L $\mathcal{F}$ (voir ce lien).
Je pense que si $\phi_g\in Aut(\mathcal{F})$ alors comme pour tout $(G,H)\in \mathcal{F}^{2}$ $\phi_g(G.H)=\phi_g(G).\phi_g(H)$, nécessairement $g$ est (complètement) multiplicative.
Donc ici on aurait $g\in\{Id,s\mapsto \overline{s}\}$.

Quelqu'un peut confirmer ?

Dans ton cas précis tu n'es pas obligé de te faire mal au cou en restant sur le cercle je pense, tu peux dérouler la configuration et regarder ce qui se passe à plat en regadant $\R / \Z$. Du coup is tu prends un nombre compris entre 0 et 1 dont la suite des décimales est uniquement composée de 0 et de 1 et dont les digits ont à part ça été tirés au sort (avec un pièce quantique, :D lool non je dec), l'adhérence de l'orbite d'un tel réel est homéomorphe à l'ensemble de tous les réels compris entre 0 et 1 dont l'écriture décimale ne s'écrit qu'avec des 0 et des 1. Tu n'as plus qu'à rédiger ça de manière à passer le couroux éventuel de tout correcteur acariatre :D

edit-précision: oups sorry j'ai mis "décimal" en gras alors que c'est un grosse bétise. Au contraire, faut écrire en binaire, et prendre des réels dont l"écriture dyadique n'est pas "tout à fait" choisie au hasard, mais presque, par exemple tu exiges qu'un 1 soit toujours suivi au minimum de 150 zéros

Citation

Pourquoi ne peut-on pas utiliser ce critère pour montrer que O(n,C) est bornée et donc compact (ce qui est faux)?

Bon je n'ai pas vraiment lu le fil, mais j'ai vu que les autres intervenants t'avaient déjà dit ce qu'il fallait sur le peu d'intérêt que les matheux accordent à la forme bilinéaire $\sum x_iy_i$ quand on est dans $\C$ et leur préfère $\sum x_iy'_i$ en notant $y'$ le conjugué de $y$.

Dans le cas réel $\sum x_i.x_i =1$ oblige chaque $x_i$ à être dans $[-1,1]$ ce qui force la compacité de $\{x / \sum x_i.x_i=1\}$.

Le même chose se produit dans le cas complexe mais avec $<x\mid y>:=\sum x_i.y'_i$ car $\sum x_i.x'_i = \sum (module (x_i))^2$

Bonsoir.
Je cherche à étudier les orbites non "périodiques (à partir d'un certain rang)" de l'application de doublement de l'angle, c'est-à-dire $$\begin{array}{rrcl}
f:&\mathbb{U}&\rightarrow&\mathbb{U}\\
& x&\mapsto& x^2
\end{array}$$ où $\mathbb{U}$ est le cercle unité.
Plus précisément, je cherche à décrire les ensembles (adhérence, équirépartition, etc) $(f^n(x_0))_{n\in\mathbb{N}}$ ($f^n$ désigne "$f$ composée $n$ fois avec elle-même") où $x_0$ est de la forme $e^{i\theta}$ avec $\theta \in \mathbb{R}\setminus\pi\mathbb{Q}$.

-> Ce que je cherche à montrer exactement, c'est que "la plupart" (en un sens à préciser) de ces orbites sont denses, mais qu'il en existe certaines dont l'adhérence est homéomorphe à l'ensemble de Cantor.

Je ne sais pas du tout comment procéder. Si vous avez des pistes de recherche où des théorèmes/notions utiles pour résoudre mon problème je suis preneur !
Merci par avance.
PS: J'ai le niveau maths spé.

@snap : Oui, c'est d'ailleurs la première idée que j'ai eue, mais je ne pense pas qu'il y ait des propriétés remarquables sur ce genre de récurrence. Intuitivement, parce qu'un choix de lignes ou de colonnes a un impact sur le reste de la solution..

@sylvain : Je vois, mais comment interpréter sur la matrice d'origine, le fait de trouver les $k$ plus grandes lignes de la matrice symétrique? En fait, je ne vois pas comment en résolvant le problème sur la matrice symétrique, on arriverait à une solution optimale.

Bien compliqué d'écrire $2(1-\int \min(f,g))$ à la place de $\int|f-g|....$

Bonsoir.

Par contraposition, si n n'est pas une puissance de 2 il s'écrit $n=p\times 2^k$ avec p impair supérieur ou égal à 3; etc.

Cordialement.

Oui, j'ai confondu alphabets grec et latin.
Et pour répondre à ta question, non, je ne vois pas "bien" que $Aut(\mathbb{Z}^d)=GL(d,\mathbb{Z})$. Si $f$ est un élément de $Aut(\mathbb{Z}^{d})$, $f^{-1}$ aussi donc on se doute que s'il existe une matrice carrée $d\times d$ $M_f$ à coefficients
entiers relatifs telle que l'application $f\mapsto M_f$ est un homomorphisme de groupe, alors le déterminant de $M_f$ est non nul. Et comme $det(M_{f^{-1}})=1/det(M_{f})$, $det(M_f)=\pm 1$. Mais je ne vois trop quoi dire de plus...
Sinon je ne suis pas très au courant des résultats d'algèbre linéaire sur un corps, donc ne vois pas trop où tu veux m'emmener.