Является ли функция многочленом?

[passs]

Есть функция $f : \mathbb Q\times\mathbb Q\mapsto \mathbb Q$ такая, что для любого фиксированного $x_0$ $f(x_0, y)$-многочлен от $y$ и для любого $y_0$ $f(x, y_0)$-многочлен от $x$. Обязательно ли $f(x,y)$-многочлен от $x$ и $y$?

[Профессор Снэйп]

Нет.

-- Вс янв 03, 2010 10:04:15 --

Пусть $q_0, q_1, \ldots$ --- все рациональные числа. Определим по шагам значения $f(x,y)$ для всех $\langle x,y \rangle \in \mathbb{Q}^2$. На шаге $t$ будем определять значения $f(x,y)$ для всех пар $\langle x,y \rangle$, таких что $x = q_t$ или $y = q_t$ и $f(x,y)$ не определено на предыдущих шагах.

Пусть $p_0(x,y), p_1(x,y), \ldots$ --- все многочлены из $\mathbb{Q}[x,y]$ (их счётное число). Дадим описание шагов.

Шаг $t$: Полагаем $f(q_t,q_t)$ равным какому-нибудь рациональному числу, отличному от $p_i(q_t,q_t)$ для всех $i \leqslant t$. Далее, найдём многочлен $p(y)$, такой что $p(y) = f(q_t,y)$ для всех $y \in \mathbb{Q}$, таких что значение $f(q_t,y)$ уже определено. Положим $f(q_t,y) = p(y)$ для всех $y \in \mathbb{Q}$. Аналогично найдём многочлен $q(x)$, такой что $q(x) = f(x,q_t)$ для всех $x \in \mathbb{Q}$, таких что значение $f(x,q_t)$ уже определено. Положим $f(x,q_t) = q(x)$ для всех $x \in \mathbb{Q}$. Перейдём к следующему шагу.

Ясно, что описанная конструкция даст нужный результат.

[RIP]

Можно ещё так. Пусть $p_n(z)\in\mathbb Q[z]$ ($n=0,1,\ldots$) --- (единственная) последовательность многочленов, удовлетворяющих условиям:
(1) $p_n(z)$ --- многочлен степени $n$ со старшим коэффициентом $1$;
(2) $p_n(q_m)=p_m(q_n)$ при $0\le m<n$.
Тогда функция $f(q_n,q_m)=p_n(q_m)=p_m(q_n)$ искомая.

[Профессор Снэйп]

Если в моей конструкции выбирать многочлены $p$ и $q$ так, чтобы они были степени $t$ и со старшим коэффициентом $1$, то вроде получится то же самое ($f(q_t,q_t)$ определять будет не нужно, оно задастся само)

Кстати, можно подумать об обобщениях. Вместо $\mathbb{Q}$ годится любое счётное поле. Для некоторых несчётных полей, например $\mathbb{R}$, это уже не так (точно где-то решали, не смог найти ссылку). Можно спросить, для каких полей утверждение выполняется? Хотя, думаю, это сложный вопрос.

[RIP]

Профессор Снэйп в сообщении #277158 писал(а):

Для некоторых несчётных полей, например $\mathbb{R}$, это уже не так (точно где-то решали, не смог найти ссылку).

http://dxdy.ru/topic5072.html
Для любого несчётного поля $f$ будет многочленом. Док-во то же самое, что и для $\mathbb R$. Пусть $F$ --- наше несчётное поле.
Тогда для любого несчётного подмножества $A\subseteq F$ найдутся несчётные (впрочем, достаточно даже бесконечности) подмножества $B_A\subseteq A$ и $C_A\subseteq A$ и многочлены $P_A(x,y)$ и $Q_A(x,y)$ такие, что $f(x,y)=P_A(x,y)$ при $(x,y)\in B_A\times F$ и $f(x,y)=Q_A(x,y)$ при $(x,y)\in F\times C_A$. При этом для любых $A_1$, $A_2$ равенство $P_{A_1}(x,y)=Q_{A_2}(x,y)$ справедливо при $(x,y)\in B_{A_1}\times C_{A_2}$, откуда получаем, что многочлены $P_A=Q_A=P$ не зависят от $A$. Тогда для любого $x_0\in F$ множество $\{y\in F\mid f(x_0,y)\ne P(x_0,y)\}$ не более чем счётно (иначе его можно взять в качестве $A$, и при $y\in C_A$ получаем $P(x_0,y)\ne f(x_0,y)=P(x_0,y)$). Следовательно, $f(x_0,y)=P(x_0,y)$ на бесконечном множестве, следовательно, при всех $y\in F$.