Compressed sensing

Isso é só uma nota mental para eu não esquecer de ler sobre o assunto, parece bastante útil:

http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/

Construções geométricas (5)

O Fábio Moreira me deu uma idéia legal para gerar um segmento de tamanho pq:

Pega um ângulo qualquer BAC, marca em AC o tamanho 1 e o tamanho q, marca em AB o tamanho p, liga 1 até p, traça uma paralela a essa reta passando por q, você tem dois triângulos semelhantes, então o ponto onde a paralela termina é pq.

Por isso, embora construir um primo p usando a addition chain seja assintoticamente igual a log2p, um composto pode ser menos que isso (um primo pode ser menos que isso se tiver um composto perto e depois você soma ou subtrai algumas unidades? não sei).

Agora só fazendo uma força bruta pra calcular mesmo.

Construções geométricas (4)

Qual o menor número de compassadas que você precisa dar pra construir um número? Para n inteiro, f(2^n)=n, f(n) deve depender da quantidade de bits 1 no número em binário, mas eu tô indo almoçar daqui a pouco e não vou fazer a conta agora.

Uepaaa! Acabei de notar que o número mínimo de compassadas é equivalente à minimal addition chain, então não apenas não tem forma fechada, como é NP-completo. E isso só pros inteiros, pra sqrt() deve ser ainda pior.

Construções geométricas (3)

Comentários do Kögler sobre os problemas:

    -você diz construir com régua e compasso em R^n. Bom, você admite réguas e compassos nD, certo ? Então admite também réguas (n-p)D e compassos (n-q)D, significa que aceita essas retas e esferas e suas intersecções.
-na sua construção da raiz em 2D, experimente 2 retas paralelas com separação unitária.Escolha um ponto de origem numa delas e marque um segmento unitário. A projeção dele na outra reta conduz ao segmento sqrt(2). Transfira-o a partir da origem para a outra reta. A projeção da nova extremidade na outra paralela produz sqrt(3). E assim por diante.12:19 pm

Em Aberto 1: Qual o menor número de compassadas que você precisa dar pra construir um número? Para n inteiro, f(2^n)=n, f(n) deve depender da quantidade de bits 1 no número em binário, mas eu tô indo almoçar daqui a pouco e não vou fazer a conta agora. E em conjunto? f(6)=2, f(8)=3, mas f(6,8)=4, porque você já construiu o 2 quando estava fazendo o 8 e pode reusar o 6. Isso é transitivo e associativo? f(m,n,p)=f(m,f(n,p))=f(f(m,n),p)? Não sei. E para sqrt(n)? Pela construção do Kögler, g(n)<=n, mas dá pra fazer com menos usando o triangulo retangulo com números apropriados.

Em Aberto 2: Considere sqrt(p/q) com p/q irredutível e sqrt(p/q) irracional. Esse conjunto é denso? Eu acho que deve ser, mas o almoço tá saindo.

Construções geométricas (2)

Dá pra construir qualquer raiz quadrada?

A: Dá sim, mas demora. Pra achar sqrt(p/q), você faz sqrt(p)/sqrt(q) usando o método do retângulo, e pra achar sqrt(p) com p inteiro tem que usar uma espiral de triângulos retângulos:

Construindo sqrt(6)

A diagonal do quadrado de lado 1 é sqrt(2). Dado que sqrt(x) existe, então você faz o triângulo retângulo de lados 1 e sqrt(x), a hipotenusa é sqrt(1+x), QED.

Eu acho que raiz cúbica irracional em dimensão 2 não dá.

Construções geométricas

Quais números você pode construir com régua e compasso num espaço n-dimensional?

Definições:

Régua: dados dois pontos, podemos construir a reta infinita que passa por eles.
Compasso: dados dois pontos, podemos construir a hiperesfera centrada em um e que passa pelo outro.

Em uma dimensão, só dá pra construir os inteiros.

Em duas dimensões, dá pra construir fácil qualquer racional p/q com essa construção:

Construindo 2/3

Prova: f(0)=0, f(p)=q, f(x)=ax+b, b=0, f(x)=ax, f(p)=pa=q, a=q/p, f(p/q)=p/q.q/p=1, QED

Dá para construir qualquer raiz quadrada? sqrt(p/q)?

Em aberto 1: Dá pra construir uma hierarquia de irracionais, associando cada um à menor dimensão que ele aparece?

Em aberto 2: Quais irracionais não são construtiveis assim? (todos os transcendentes, ou tem algébrico que não dá)?

Em aberto 3: E em geometrias não-euclideanas? Como definir régua e compasso?

Em aberto 4: Dimensões fracionárias?

Start

Às vezes eu tenho idéias que ficam pela metade. Algumas vezes por falta de habilidade, outras simplesmente por ovelhice mesmo, eu não anoto em lugar algum e acabo esquecendo. Aí eu pensei que seria bom ter um canto para anotar as idéias que surgem.

Esse blog não é o Brain Dump. No Brain Dump os posts tem começo, meio, fim, e desenho. Aqui a idéia é que tenham só começo e meio, às vezes só começo, e por vezes nem isso, só idéias soltas mesmo.

Na verdade, a maior motivação para criar esse blog é que