Poset(Under Construction!)

Poset

數列推廣成偏序集(反擬陣?)。

一個偏序集,子集合總和(偏序集積分)、子集合排容(偏序集微分),互為反運算。

積分前摺積 = 積分後乘法。定義祖性摺積:令兩元素的結合結果是最低共同祖先LCA。數列摺積的結合運算子是加法、乘法,偏序集摺積則是LCA。

https://mycourses.aalto.fi/mod/resource/view.php?id=90388

引入cyclic inclusion-exclusion就滿足對偶了?此時偏序集積分的效果等同於FFT、FNT等轉換。

Invitation to Algorithmic Uses of Inclusion–Exclusion
https://arxiv.org/abs/1105.2942

範例

當偏序集是子集關係。結合運算子是聯集。

當偏序集是分割數(組合數)關係,此定理即是巴斯卡三角形。

當偏序集是因數關係,此定理即是Möbius inversion formula。此時偏序集微積分可以寫成乘性摺積:積分是摺以常數函數1,微分是摺以Möbius function μ。結合運算子是最小公倍數。

    偏序集積分
    --------->
 祖 |        | 點
 性 |        | 乘
 摺 |        |        我猜是這樣
 積 v        v
    <---------
    偏序集微分
   乘性摺積(因數關係)

Sequence + Poset

當偏序集是數列項次的因數關係。

原數列每一項除以(1+xⁱ)後z轉換,等於積分後z轉換。左式叫做Lambert series。

原數列ζ轉換、再乘上一個倍率ζ(s),等於積分後ζ轉換。

反元素:

ζ(s) = sum 1/(nˢ)
1/ζ(s) = sum u(n)/(nˢ)

Euler Product

歐拉加乘對偶。

最大公因數的傅立葉轉換就是Euler's Totient Function

http://en.wikipedia.org/wiki/Euler%27s_totient_function#Fourier_transform

       N-1
φ(n) =  ∑ { gcd(n, k) ÷ ei⋅2π⋅(n/N)⋅k }
       k=0

因數與乘性摺積

constant function 1: 1(1) = 1(2) = ... = 1
identity function I: I(n) = n
divisor function τ: τ(n) = # of divisors of n
totient function φ: φ(n) = # of relative prime of n
1 ∗ 1 = σ₀ = τ   divisor count

φ ∗ 1 = I        x
I ∗ 1 = σ₁ = σ   divisor sum

ICPC 7837

Matroid(Under Construction!)

Antimatroid

反擬陣。廣義遞迴關係。許多集合,層層包含。

可以畫成有向無環圖(層數是集合大小),整體呈菱形結構。

1. 隨便抓個集合,刪除某個元素,也要被包含 = 子集合也要被包含
2. 隨便抓兩個集合,聯集也要被包含
向下 規則1.
給兩三個大集合,可以有交集
每個大集合都要窮舉各種子集合,生一堆子子孫孫出來
終點(匯)顯然是空集合

向上 規則2.
給兩三個大集合,可以有交集
兩兩大集合都要窮舉各種聯集,生一堆父父祖祖出來
起點(源)顯然是宇集合

Matroid

擬陣。廣義遞迴關係。許多集合,層層包含。

可以畫成有向無環圖(層數是集合大小),整體呈菱形結構。

1. 隨便抓個集合,刪除某個元素,也要被包含 = 子集合也要被包含
2. 隨便抓兩個集合,隨便從差集找到某個元素,然後小集合添上元素,也要被包含
   隨便抓兩個集合,交集+差集子集也要被包含
1. 子集合通通不可被包含  除了空集合
2. 聯集-交集也要被包含

Fourier Transform(Under Construction!)

Fourier Transform

傅立葉轉換是一對一函數,輸入和輸出都是一串複數。

請見本站文件「Fourier Transform」。

e的純虛數次方會不斷繞圈。採用單位根的次方ei⋅2π/N

複數 垂直座標  轉換機制  頻率座標  轉換名稱  時間複雜度
一一 一一一一一 一一一一一 一一一一一 一一一一一 一一一一一
數字 實部、虛部 長度、角度 幅長、幅角 極轉換   O(1)
函數 實部、虛部 複數波   強度、相位 傅立葉轉換 O(NlogN)
e^x               輸入相加=輸出相乘
fourier transform 輸入點積=輸出摺積

傅立葉轉換也許可以視作座標系轉換。有些問題在垂直座標很難算,在頻率座標卻很好算。複數乘法變長度相乘、角度相加。數列摺積變數列乘法。

傅立葉轉換是積分變換,可以視作向量空間的座標系。

Eigenvalue與Fourier Transform

循環矩陣,特徵向量是傅立葉矩陣,特徵值是第一個橫條的傅立葉轉換。

http://math.stackexchange.com/questions/25126/

1. 兩個循環矩陣相乘  = 總是可以用fourier matrix作對角化 = 對角線矩陣相乘
  (還是循環矩陣)        (C = F D F⁻¹) (F⁻¹ = Fᵀ)       (對應的eigenvalue相乘)

2. 兩串數列的循環摺積     = fft                         = 對應項相乘

3. 兩個多項式的循環乘法   = 多項式求值,以e^-itn取樣  = 對應的點座標相乘

4. 兩串函數值的循環乘法   = 這是甚麼東西?

5. 兩串分解式的循環乘法   = 這是甚麼東西?
   (2n個根融合成n個根)
tridiagonal and Toeplitz matrix's eigenvalues:
a + 2 sqrt(bc) cos(k pi / (n+1))   for k = 1~n
eigenvectors of fourier matrix is gaussian function
eigenvalues of fourier matrix is +1 -1 +i -i
F^4 = I

Convolution(Under Construction!)

Convolution

pairwise binding (+/x), paiwise operation (x), merge operation (+)
+x+: linear convolution      fft/fnt
xx+: dirichlet convolution   brute force     mobius, ui principle, ...
linear convolution: 加法分解
Dirichlet convolution: 乘法分解

單位元素、反元素

加性摺積當中,單位元素是脈衝函數δ。

impulse function δ: δ(0) = 1; δ(±1) = δ(±2) = ... = 0
f ∗ g = δ  g是加性摺積反元素

乘性摺積當中,單位元素是脈衝函數ε。

常數函數1的反元素是乘性排容函數Möbius function。

impulse function ε: ε(1) = 1; ε(2) = ε(3) = ... = 0
f ∗ g = ε  g是乘性摺積反元素
μ ∗ 1 = ε

延伸閱讀:Bitwise XOR Convolution

結合運算子從加法、乘法改成了程式語言的^異或運算子。又稱作dyadic convolution或logical convolution。

矩陣形式是Hadamard matrix或Walsh matrix。數值都是±1而且向量互相垂直(點積為零)。

轉換名稱叫做Hadamard transform或Walsh transform。因為沒有循環,所以沒有對偶?

http://book.huihoo.com/pdf/algorithms-for-programmers/afp.pdf   p362 $9.6
http://iris.elf.stuba.sk/JEEEC/data/pdf/09-10_102-10.pdf
http://en.wikipedia.org/wiki/Hadamard_matrix
https://en.wikipedia.org/wiki/Dyadic_rational
http://www.jjj.de/fxt/fxtbook.pdf

延伸閱讀:Infimal Convolution

linear convolution:加法結合,數值相乘,加法累計。
dirichlet convolution:乘法結合,數值相乘,加法累計。
bitwise XOR convolution:XOR結合,數值相乘,加法累計。
infimal convolution: 加法結合,函數加法,下界累計。Minkowski sum。

Fourier Ramanujan Transform

http://perso.ens-lyon.fr/patrick.flandrin/NewOrl2.pdf

複數波改成Ramanujan Sum。

norm從N改成φ(n)。垂直是互質。逆轉換需要定義無限長數列的內積。

Hadamard Transform

Laplace Transform

波粒二象性是脈衝函數做拉普拉斯轉換?