3.3.md

$p = 11$의 유한체 위로 가정한다.

where $v = 2$

$\mathbb B^2$를 2차원 binary hypercube라고 하자. $\mathbb B$의 모든 원소에 대해 아래 함숫값들은 알려져 있다.

$$\begin{aligned} f(0, 0) &= 3 \\ f(0, 1) &= 4 \\ f(1, 0) &= 1 \\ f(1, 1) &= 2 \\ \end{aligned}$$

Lemma 3.6에 기반해 MLE를 구한다.

우선 다음을 전개하고

$$\begin{aligned} \chi_w(x_1, x_2) &= \prod^2_{i = 1}x_i w_i + (1 - x_i)(1 - w_i) \\ &= (x_1 w_1 + (1 - x_1)(1 - w_1)) (x_2 w_2 + (2 - x_2)(2 - w_2)) \\ \end{aligned}$$

이어

$$\begin{array}{ll} \tilde f(x_1, x_2) &=& \displaystyle\sum_{w \in {0, 1}^2} f(w) \chi_w(x_1, x_2) \\ &=& 3 \chi_{(0, 0)}(x_1, x_2) + \\ && 4 \chi_{(0, 1)}(x_1, x_2) + \\ && 1 \chi_{(1, 0)}(x_1, x_2) + \\ && 2 \chi_{(1, 1)}(x_1, x_2) + \\ &=& 3 (0 x_1 + (1 - x_1)(1 - 0)) (0 x_2 + (2 - x_2)(2 - 0)) + \\ && 4 (0 x_1 + (1 - x_1)(1 - 0)) (1 x_2 + (2 - x_2)(2 - 1)) + \\ && 1 (1 x_1 + (1 - x_1)(1 - 1)) (0 x_2 + (2 - x_2)(2 - 0)) + \\ && 2 (1 x_1 + (1 - x_1)(1 - 1)) (1 x_2 + (2 - x_2)(2 - 1)) + \\ &=& 3 - 2x_1 + x_2 \\ \end{array}$$

따라서 $\tilde f(2, 4) = 3$.

where $v = 3$

첨부된 코드 구현 vsbw.ts 참고.

vsbw.ts

const chi = (p: number, r: Array<number>) => {
	const mems = [[1 - r[0], r[0]]]

	for (let i = 1; i < r.length; ++i)
		for (let j = ((mems[i] = []), 0); j < 2 ** i; ++j) {
			mems[i][j * 2] = (mems[i - 1][j] * (1 - r[i])) % p
			mems[i][j * 2 + 1] = (mems[i - 1][j] * r[i]) % p
		}

	return mems.at(-1)!
}

const vsbw = (p: number, fw: Array<number>, r: Array<number>) =>
	chi(p, r)
		.map((chiW, i) => chiW * fw[i])
		.reduce((a, b) => (a + b) % p, 0)

const p = 11
const fw = [1, 5, 2, 6, 3, 7, 4, 8]
const r = [2, 4, 6]

// verify that ~f actually extends f
for (let i = 0; i < fw.length; ++i)
	console.assert(vsbw(p, fw, [(i >> 2) & 1, (i >> 1) & 1, i & 1]) === fw[i])

console.log(vsbw(p, fw, r))