% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{fact}[thm]{Fact}
\newtheorem{observation}[thm]{Observation}
\newtheorem{claim}[thm]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{open}[thm]{Open Problem}
\newtheorem{problem}[thm]{Problem}
\newtheorem{question}[thm]{Question}



\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem{note}[thm]{Note}



%\documentclass[12pt]{article}
%\usepackage{e-jc,amsthm,amsmath,amssymb}

%\documentclass{amsart}
%\usepackage{amssymb}
\title{The Combinatorial Nullstellens\"atze Revisited}


\author{Pete L. Clark\\
\small Department of Mathematics\\[-0.8ex]
\small University of Georgia\\[-0.8ex] 
\small Athens, GA, U.S.A.\\
\small\tt plclark@gmail.com\\
%\and
%Forgotten Second Author \qquad  Forgotten Third Author\\
%\small School of Hard Knocks\\[-0.8ex]
%\small University of Western Nowhere\\[-0.8ex]
%\small Nowhere, Australasiaopia\\
%\small\tt \{fsa,fta\}@uwn.edu.ao
}


%\author{Pete L. Clark}\\
%\small Department of Mathematics\\[-0.8ex]
%\small University of Georgia\\[-0.8ex] 
%\small Athens, GA U.S.A.\\
%\small\tt plclark@gmail.com\\

\date{\dateline{INSERT}{INSERT}\\
\small Mathematics Subject Classifications: 11T55, 13B25}


%\author{Pete L. Clark}
\begin{document}
%\newtheorem{lemma}{Lemma}[section]
%\newtheorem{prop}[lemma]{Proposition}
%\newtheorem{cor}[lemma]{Corollary}
%\newtheorem{thm}[lemma]{Theorem}
%\newtheorem{ques}{Question}
%\newtheorem{quest}[lemma]{Question}
%\newtheorem{conj}[lemma]{Conjecture}
%\newtheorem{fact}[lemma]{Fact}
%\newtheorem{definition}[lemma]{Definition}
%\newtheorem*{mainthm}{Main Theorem}
%\newtheorem*{unthm}{Theorem}
%\newtheorem{obs}[lemma]{Observation}
%\newtheorem{hint}{Hint}
%\newtheorem{remark}[lemma]{Remark}
%\newtheorem{example}[lemma]{Example}





%
\newcommand{\pp}{\mathfrak{p}}
%\renewcommand{\gg}{\mathfrak{g}}
\newcommand{\DD}{\mathcal{D}}
\newcommand{\F}{\ensuremath{\mathbb F}}
\newcommand{\Fp}{\ensuremath{\F_p}}
\newcommand{\Fl}{\ensuremath{\F_l}}
\newcommand{\Fpbar}{\overline{\Fp}}
\newcommand{\Fq}{\ensuremath{\F_q}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\PPone}{\mathfrak{p}_1}
\newcommand{\PPtwo}{\mathfrak{p}_2}
\newcommand{\PPonebar}{\overline{\PPone}}
\newcommand{\N}{\ensuremath{\mathbb N}}
\newcommand{\Q}{\ensuremath{\mathbb Q}}
\newcommand{\Qbar}{\overline{\Q}}
\newcommand{\R}{\ensuremath{\mathbb R}}
\newcommand{\Z}{\ensuremath{\mathbb Z}}
\newcommand{\SSS}{\ensuremath{\mathcal{S}}}
\newcommand{\Rn}{\ensuremath{\mathbb R^n}}
\newcommand{\Ri}{\ensuremath{\R^\infty}}
\newcommand{\C}{\ensuremath{\mathbb C}}
\newcommand{\Cn}{\ensuremath{\mathbb C^n}}
\newcommand{\Ci}{\ensuremath{\C^\infty}}\newcommand{\U}{\ensuremath{\mathcal U}}
\newcommand{\gn}{\ensuremath{\gamma^n}}
\newcommand{\ra}{\ensuremath{\rightarrow}}
\newcommand{\fhat}{\ensuremath{\hat{f}}}
\newcommand{\ghat}{\ensuremath{\hat{g}}}
\newcommand{\hhat}{\ensuremath{\hat{h}}}
\newcommand{\covui}{\ensuremath{\{U_i\}}}
\newcommand{\covvi}{\ensuremath{\{V_i\}}}
\newcommand{\covwi}{\ensuremath{\{W_i\}}}
\newcommand{\Gt}{\ensuremath{\tilde{G}}}
\newcommand{\gt}{\ensuremath{\tilde{\gamma}}}
\newcommand{\Gtn}{\ensuremath{\tilde{G_n}}}
\newcommand{\gtn}{\ensuremath{\tilde{\gamma_n}}}
\newcommand{\gnt}{\ensuremath{\gtn}}
\newcommand{\Gnt}{\ensuremath{\Gtn}}
\newcommand{\Cpi}{\ensuremath{\C P^\infty}}
\newcommand{\Cpn}{\ensuremath{\C P^n}}
\newcommand{\lla}{\ensuremath{\longleftarrow}}
\newcommand{\lra}{\ensuremath{\longrightarrow}}
\newcommand{\Rno}{\ensuremath{\Rn_0}}
\newcommand{\dlra}{\ensuremath{\stackrel{\delta}{\lra}}}
\newcommand{\pii}{\ensuremath{\pi^{-1}}}
\newcommand{\la}{\ensuremath{\leftarrow}}
\newcommand{\gonem}{\ensuremath{\gamma_1^m}}
\newcommand{\gtwon}{\ensuremath{\gamma_2^n}}
\newcommand{\omegabar}{\ensuremath{\overline{\omega}}}
\newcommand{\dlim}{\underset{\lra}{\lim}}
\newcommand{\ilim}{\operatorname{\underset{\lla}{\lim}}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\Ext}{\operatorname{Ext}}
\newcommand{\Part}{\operatorname{Part}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\unr}{\operatorname{unr}}
\newcommand{\B}{\ensuremath{\mathcal B}}
\newcommand{\Ocr}{\ensuremath{\Omega_*}}
\newcommand{\Rcr}{\ensuremath{\Ocr \otimes \Q}}
\newcommand{\Cptwok}{\ensuremath{\C P^{2k}}}
\newcommand{\CC}{\ensuremath{\mathcal C}}
\newcommand{\gtkp}{\ensuremath{\tilde{\gamma^k_p}}}
\newcommand{\gtkn}{\ensuremath{\tilde{\gamma^k_m}}}
\newcommand{\QQ}{\ensuremath{\mathcal Q}}
\newcommand{\I}{\ensuremath{\mathcal I}}
\newcommand{\sbar}{\ensuremath{\overline{s}}}
\newcommand{\Kn}{\ensuremath{\overline{K_n}^\times}}
\newcommand{\tame}{\operatorname{tame}}
\newcommand{\Qpt}{\ensuremath{\Q_p^{\tame}}}
\newcommand{\Qpu}{\ensuremath{\Q_p^{\unr}}}
\newcommand{\scrT}{\ensuremath{\mathfrak{T}}}
\newcommand{\That}{\ensuremath{\hat{\mathfrak{T}}}}
\newcommand{\Gal}{\operatorname{Gal}}
\newcommand{\Aut}{\operatorname{Aut}}
\newcommand{\tors}{\operatorname{tors}}
\newcommand{\Zhat}{\hat{\Z}}
\newcommand{\linf}{\ensuremath{l_\infty}}
\newcommand{\Lie}{\operatorname{Lie}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\aone}{\ensuremath{(a_1,\ldots,a_k)}}
\newcommand{\raone}{\ensuremath{r(a_1,\ldots,a_k,N)}}
\newcommand{\rtwoplus}{\ensuremath{\R^{2  +}}}
\newcommand{\rkplus}{\ensuremath{\R^{k +}}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\cross}{\operatorname{cross}}
\newcommand{\GoN}{\Gamma_0(N)}
\newcommand{\GeN}{\Gamma_1(N)}
\newcommand{\GAG}{\Gamma \alpha \Gamma}
\newcommand{\GBG}{\Gamma \beta \Gamma}
\newcommand{\HGD}{H(\Gamma,\Delta)}
\newcommand{\Ga}{\mathbb{G}_a}
\newcommand{\Div}{\operatorname{Div}}
\newcommand{\Divo}{\Div_0}
\newcommand{\Hstar}{\cal{H}^*}
\newcommand{\txon}{\tilde{X}_0(N)}
\newcommand{\sep}{\operatorname{sep}}
\newcommand{\notp}{\not{p}}
\newcommand{\Aonek}{\mathbb{A}^1/k}
\newcommand{\Wa}{W_a/\mathbb{F}_p}
\newcommand{\Spec}{\operatorname{Spec}}

\newcommand{\abcd}{\left[ \begin{array}{cc}
a & b \\
c & d
\end{array} \right]}

\newcommand{\abod}{\left[ \begin{array}{cc}
a & b \\
0 & d
\end{array} \right]}

\newcommand{\unipmatrix}{\left[ \begin{array}{cc}
1 & b \\
0 & 1
\end{array} \right]}

\newcommand{\matrixeoop}{\left[ \begin{array}{cc}
1 & 0 \\
0 & p
\end{array} \right]}

\newcommand{\w}{\omega}
\newcommand{\Qpi}{\ensuremath{\Q(\pi)}}
\newcommand{\Qpin}{\Q(\pi^n)}
\newcommand{\pibar}{\overline{\pi}}
\newcommand{\pbar}{\overline{p}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\trace}{\operatorname{trace}}
\newcommand{\OKv}{\mathcal{O}_{K_v}}
\newcommand{\Abarv}{\tilde{A}_v}
\newcommand{\kbar}{\overline{k}}
\newcommand{\Kbar}{\overline{K}}
\newcommand{\pl}{\rho_l}
\newcommand{\plt}{\tilde{\pl}}
\newcommand{\plo}{\pl^0}
\newcommand{\Du}{\underline{D}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\D}{\underline{D}}
\newcommand{\op}{\operatorname{op}}
\newcommand{\Glt}{\tilde{G_l}}
\newcommand{\gl}{\mathfrak{g}_l}
\newcommand{\gltwo}{\mathfrak{gl}_2}
\newcommand{\sltwo}{\mathfrak{sl}_2}
\newcommand{\h}{\mathfrak{h}}
\newcommand{\tA}{\tilde{A}}
\newcommand{\sss}{\operatorname{ss}}
\newcommand{\X}{\Chi}
\newcommand{\ecyc}{\epsilon_{\operatorname{cyc}}}
\newcommand{\hatAl}{\hat{A}[l]}
\newcommand{\sA}{\mathcal{A}}
\newcommand{\sAt}{\overline{\sA}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\OOB}{\OO_B}
\newcommand{\Flbar}{\overline{\F_l}}
\newcommand{\Vbt}{\widetilde{V_B}}
\newcommand{\XX}{\mathcal{X}}
\newcommand{\GbN}{\Gamma_\bullet(N)}
\newcommand{\Gm}{\mathbb{G}_m}
\newcommand{\Pic}{\operatorname{Pic}}
\newcommand{\FPic}{\textbf{Pic}}
\newcommand{\solv}{\operatorname{solv}}
\newcommand{\Hplus}{\mathcal{H}^+}
\newcommand{\Hminus}{\mathcal{H}^-}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\Alb}{\operatorname{Alb}}
\newcommand{\FAlb}{\mathbf{Alb}}
\newcommand{\gk}{\mathfrak{g}_k}
\newcommand{\car}{\operatorname{char}}
\newcommand{\Br}{\operatorname{Br}}
\newcommand{\gK}{\mathfrak{g}_K}
\newcommand{\coker}{\operatorname{coker}}
\newcommand{\red}{\operatorname{red}}
\newcommand{\CAY}{\operatorname{Cay}}
\newcommand{\ns}{\operatorname{ns}}
\newcommand{\xx}{\mathbf{x}}
\newcommand{\yy}{\mathbf{y}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\rad}{\operatorname{rad}}
\newcommand{\Top}{\operatorname{Top}}
\newcommand{\Map}{\operatorname{Map}}
\newcommand{\Li}{\operatorname{Li}}
\renewcommand{\Map}{\operatorname{Map}}
\newcommand{\ZZ}{\mathcal{Z}}
\newcommand{\uu}{\mathfrak{u}}
\newcommand{\mm}{\mathfrak{m}}
%$\begin{CD}
%E @>{\tau_P}>> E \\
%@V{\varphi}VV @VV{\varphi}V \\
%\PP^{n-1} @>{\gamma(\tau_P)}>> \PP^{n-1}
%\end{CD}$
\newcommand{\zz}{\mathbf{z}}
\newcommand{\Image}{\operatorname{Image}}
\newcommand{\cc}{\mathfrak{c}}
\newcommand{\ii}{\mathfrak{i}}
\renewcommand{\ss}{\mathfrak{s}}
\renewcommand{\cc}{\mathbf{c}}
\newcommand{\dd}{\mathbf{d}}
\newcommand{\ee}{\mathbf{e}}

\maketitle

\begin{abstract}
We revisit and further explore the celebrated Combinatorial Nullstellens\"atze of N. Alon in several different directions. 
\end{abstract}



\noindent
\textbf{Notation and Terminology:} Let $\mathbb{N}$ be the non-negative integers.  For $\dd = (d_1,\ldots,d_n), \ee = (e_1,\ldots,e_n) \in \N^n$, we write $\dd \leq \ee$ if $d_i \leq e_i$ for all $1 \leq i \leq n$.  We write 
$\dd < \ee$ if $\dd \leq \ee$ and $\sum_{i=1}^n d_i < \sum_{i=1}^n e_i$.  Our rings are commutative with multiplicative identity.  A \textbf{domain} is a ring $R$ in which
$a,b \in \R \setminus \{0\} \implies ab \neq 0$.   A ring $R$ is \textbf{reduced} if for all $x \in R, n \in \Z^+$, we have $x^n = 0 \implies x = 0$.  We abbreviate the polynomial ring $R[t_1,\ldots,t_n]$ by $R[\underline{t}]$. 

\section{Introduction}

\subsection{The Combinatorial Nullstellens\"atze}
%\textbf{} \\ \\ \noindent
This note concerns the following celebrated results of N. Alon.  

\begin{thm}
%\label{11.6.3}
\label{11.7.2}
\label{CN}
\label{CNI}
Let $F$ be a field, let $X_1,\ldots,X_n \subset F$ be nonempty and finite, and $X = \prod_{i=1}^n X_i$.  For $1 \leq i \leq n$, put
\begin{equation}
\label{DIAGONALPHIEQ}
 \varphi_i(t_i) = \prod_{x_i \in X_i} (t_i-x_i) \in F[t_i] \subset F[\underline{t}].
\end{equation}
Let $f \in F[\underline{t}]$ be a polynomial which vanishes on all the common zeros of $\varphi_1,\ldots,\varphi_n$: that is, for all $x \in F^n$, if $\varphi_1(x) = \ldots = \varphi_n(x) = 0$, then $f(x) = 0$.  Then: \\
a) (Combinatorial Nullstellensatz I, or \textbf{CNI}) There are $q_1,\ldots,q_n \in F[\underline{t}]$ such that
\begin{equation} f(t) = \sum_{i=1}^n q_i(t) \varphi_i(t). 
\end{equation}
b) (Supplementary Relations) Let $R$ be the subring of $F$ generated by the coefficients of $f$ and $\varphi_1,\ldots,\varphi_n$.  Then the $q_1,\ldots,q_n$ may be chosen to lie in $R[\underline{t}]$ and satisfy
\begin{equation}
\label{SUPPLEMENTEQ}
\forall 1 \leq i \leq n, \ \deg q_i \leq \deg f - \deg \varphi_i. 
\end{equation}
%c) Moreover, if $R$ is a subring of $F$ containing all the coefficients of 
%$f$ and $\varphi_1,\ldots,\varphi_n$, then the $q_1,\ldots,q_n 
\end{thm}
%\noindent
%Using Theorem \ref{CN}, Alon deduced the following result.

\begin{thm}(Combinatorial Nullstellensatz II, or \textbf{CNII})
%\label{11.6.4}
\label{11.7.4}
\label{PM}
\label{CNII}
Let $F$ be a field, $n \in \Z^+$, $d_1,\ldots,d_n \in \N$, and let $f \in F[\underline{t}] = F[t_1,\ldots,t_n]$.  We suppose: \\
(i) $\deg f \leq d_1 + \ldots + d_n$.  \\
(ii) The coefficient of $t_1^{d_1} \cdots t_n^{d_n}$ in $f$ is nonzero.  \\
Then, for any subsets $X_1,\ldots,X_n$ of $F$ with $\# X_i = d_i+1$ for $1 \leq i \leq n$, there is $x = (x_1,\ldots,x_n) \in X = \prod_{i=1}^n X_i$ such that 
$f(x) \neq 0$.
\end{thm}
%\begin{proof} Seeking a contradiction, suppose $f(a) = 0$ for all $a \in A$.  %For $1 \leq i \leq n$, put \[\varphi_i(t_i) = \prod_{a_i \in A_i} t_i - a_i. \] 
%Since $A$ is precisely 
%the set of common zeros of $g_1,\ldots,g_n$, Theorem \ref{CN} applies, and %there are $q_1,\ldots,q_n \in F[\underline{t}]$ such that 
%\[ f = \sum_{i=1}^n q_i \varphi_i \]
%and 
%\begin{equation}
%\label{POLYMETHEQ}
%\forall 1 \leq i \leq n, \ \deg h_i \varphi_i \leq \deg f \leq a_1 + \ldots + a_n.
%\end{equation}
%Thus if $h_i \varphi_i$  contains any monomial of degree $a_1+\ldots+a_n$, such a %monomial would be a term of maximal degree in $h_i \varphi_i =  h_i  \prod_{a_i \in %A_i} (t_i -s_i)$ and thus be divisible by $t_i^{a_i+1}$.  It follows that for %all $i$,  the coefficient of $t_1^{a_1} \cdots t_n^{a_n}$ in $h_i \varphi_i$ is zero, %and thus the coefficient of $t_1^{a_1} \cdots t_n^{a_n}$ in $f$ is zero, %contradicting (ii).
%\end{proof}
\noindent
Alon used his Combinatorial Nullstellens\"atze to derive various old and new results in number theory and combinatorics, starting with Chevalley's Theorem that a homogeneous polynomial of degree $d$ in at least $d+1$ variables over a finite field has a nontrivial zero.  The use of polynomial methods has burgeoned to a remarkable degree in recent years.  We recommend the recent survey \cite{Tao14}, which lucidly describes the main techniques but also captures the sense of awe and excitement at the extent to which these very simple ideas have cracked open the field of combinatorial number theory and whose range of future applicability seems almost boundless. 
%\\ \\
%Our nomenclature ``Combinatorial Nullstellensatz I'', ``Supplementary Relations'' %and ``Combinatorial Nullstellensatz II'' is not standard: in \cite{Alon99}, the %term ``Combinatorial Nullstellensatz'' applied equally to Theorems \ref{CN} and 
%\ref{PM}. 
\\ \\
%Of Theorems \ref{CN} and \ref{PM}, Theorem \ref{CN} is stronger: 
One easily deduces CNII from CNI and the Supplementary Relations, but (apparently) not conversely.  For appplications in combinatorics and number theory, CNII seems more useful: \cite{Alon99} organizes its applications into seven different sections, and only in the last is CNI applied.  Most later works simply refer to Theorem \ref{PM} as the Combinatorial Nullstellensatz.  We find this trend somewhat unfortunate.  On the one hand, CNI is stronger and does have some applications in its own right.  On the other hand, it is CNI which is really a Nullstellensatz in the sense of algebraic geometry, and we find this geometric connection interesting and suggestive.
\\ \\
Recently attention has focused on the following sharpening of CNII due to 
Schauz, Lason and Karasev-Petrov \cite[Thm. 3.2]{Schauz08a}, \cite[Thm. 3]{Lason10}, \cite[Thm. 4]{Karasev-Petrov12}.

\begin{thm}(Coefficient Formula)
\label{COEFFTHM}
Let $F$ be a field, and let $f \in F[\underline{t}]$.  Let 
$d_1,\ldots,d_n \in \N$ be such that $\deg f \leq d_1 + \ldots + d_n$.  For 
each $1 \leq i \leq n$, let $X_i \subset F$ with $\# X_i = d_i + 1$, and let $X = \prod_{i=1}^n X_i$.   Let $\dd = (d_1,\ldots,d_n)$, and let $c_{\dd}$ be the coefficient of $t_1^{d_1} \cdots t_n^{d_n}$ 
in $f$.  Then
\begin{equation}
\label{COEFF}
 c_{\dd} = \sum_{x = (x_1,\ldots,x_n) \in X} \frac{f(x)}{\prod_{i=1}^n \varphi_i'(x_i)}.
\end{equation}
%b) \cite[Thm. 1.3]{Schauz08} Suppose $F = A_1 = \ldots = A_n = \F_q$, so $\deg %f \leq (q-1)n$.  Then:
%\[ c_{\dd} = c_{q-1,\ldots,q-1} = (-1)^n \int f = (-1)^n \sum_{x \in \F_q^n} f(x). %
\end{thm} 
\noindent
%Some applications of Theorem \ref{COEFFTHM} seem difficult to obtain directly %from CNII. 
%\\ \\
In this note we revisit and further explore these theorems, in three 
different ways.
\\ \\
$\bullet$ In $\S 2$ we improve CNI to a full Nullstellensatz for polynomial functions on arbitrary finite subsets $X \subset F^n$ over a field $F$ (Theorem \ref{FRN}).  When $F = \F_q$, $X = \F_q^n$ we recover the \textbf{Finite Field Nullstellensatz} of G. Terjanian (Corollary \ref{FFN}). 
\\ \\
% A little reflection shows that
%Under this hypothesis he also established the \textbf{Atomic Formula}.
$\bullet$ CNI and CNII hold with $F$ replaced by any domain $R$.  Schauz showed that 
Theorem \ref{COEFFTHM} holds over any \emph{ring} $R$ so long as $X$ satisfies 
``Condition (D)'': no two distinct elements of any $X_i$ differ by a zero-divisor.    Moreover, one can view Alon's proof of CNI and CNII as a restricted variable analogue of Chevalley's proof of Chevalley's Theorem, and Schauz's work shows that one can do this over any ring with Condition (D) in hand.  We do so in $\S 3$: following Chevalley, we establish versions of Theorems \ref{CNI}, \ref{CNII} and \ref{COEFFTHM} over any ring.  It turns out that Condition (D) is necessary and sufficient for Theorem \ref{CNI} to hold.  On the other hand, if we clear denominators in (\ref{COEFF}) we get a formula which is meaningful even in the absence of Condition (D).  This Integral Coefficient Formula (Theorem \ref{GENCOEFFTHM}b)) follows by ``the permanence of algebraic identities''.  We close up this circle of ideas by establishing a 
\textbf{Restricted Variable Chevalley-Warning Theorem} (Theorem \ref{RESVARCHEV}), a refinement of the Restricted Variable Chevalley Theorem \cite{Schauz08a}, \cite{Brink11} which is complementary to the Restricted Variable Warning's Second Theorem \cite{CFS14}.
\\ \\
$\bullet$ In $\S 4$ we further analyze the evaluation map from 
polynomials to functions on an arbitrary subset $X \subset R^n$ for an arbitrary ring.  We aim to show that the (perhaps rather arid-looking) formalism of a restricted variable Nullstellensatz leads to interesting open problems in polynomial interpolation over 
commutative rings.


%\begin{cor}(Schauz \cite[Cor. 3.4]{Schauz08a})
%\label{FORROWSCHMITTCOR}
%\label{KEYSCHAUZCOR}
%Let $F$ be a field, and let $f \in F[\underline{t}]$.  Let $X_1,\ldots,X_n$ be nonempty finite %subsets of $F$ such that $\sum_{i=1}^n (\# X_i -1) > \deg f$.  Let $\mathfrak{u}_X %= \#\{ x \in X \mid f(x) \neq 0\}$.  
%Then $\mathfrak{u}_X \neq 1$.  
%\end{cor}
%\noindent
%(So if $P \in \F_q[t_1,\ldots,t_n]$ has degree $d < n$, apply 
%Corollary \ref{KEYSCHAUZCOR} with $X_1 = \ldots = X_n = \F_q$ and $f(t) = %1-P(t)^{q-1}$, and note that $f(x) = 1$ if $P(x) = 0$ and 
%$f(x) = 0$ otherwise.  Thus $P$ cannot have precisely one zero, proving Chevalley's %Theorem!)
%%\noindent
%From Corollary \ref{KEYSCHAUZCOR} one deduces Chevalley's Theorem in two lines.
%\\ \\
%Thus the lack of interest in Theorem \ref{CN} \emph{per se} seems likely to %continue.

\section{A Nullstellensatz for Finitely Restricted Polynomial Functions}

\subsection{Alon's Nullstellensatz versus Hilbert's Nullstellensatz}
%\textbf{} \\ \\ \noindent
The prospect of improving Theorem \ref{CN} \emph{as a Nullstellensatz} has not been explored, perhaps because the notion of a Nullstellensatz, though seminal in algebra and geometry, is less familiar to researchers in combinatorics.  But it was certainly familiar to Alon, who 
began \cite{Alon99} by recalling the following result.

\begin{thm}(Hilbert's Nullstellensatz)
\label{HN}
Let $F$ be an algebraically closed field, let $g_1,\ldots,g_m \in F[\underline{t}]$, and let $f \in F[\underline{t}]$ be a polynomial which vanishes 
on all the common zeros of $g_1,\ldots,g_m$.  Then there is $k \in \Z^+$ 
and $q_1,\ldots,q_m \in F[\underline{t}]$ such that 
\[ f^k = \sum_{i=1}^m q_i g_i. \]
\end{thm}
\noindent
Let us compare Theorems \ref{CN} and \ref{HN}.  They differ in the following points:  \\
$\bullet$ In Theorem \ref{CN}, $F$ can be any field.  In Hilbert's Nullstellensatz, $F$ must be algebraically closed.  Really must: if not, there is a nonconstant 
polynomial $g(t_1)$ without roots in $F$; taking $m = 1$, $g_1 = g$ 
and $f = 1$, the conclusion fails.  \\
$\bullet$ In CNI, the conclusion is that $f$ itself is a 
linear combination of the $\varphi_i$'s with polynomial coefficients, but in 
Hilbert's Nullstellensatz we must allow taking a power of $f$.  Really must: 
e.g. take $k \in \Z^+$, $m = 1$, $g_1 = t_1^k$ and $f = t_1$.  \\
$\bullet$ The Supplementary Relations give upper bounds on the degrees of 
the polynomials $q_i$: they make CNI \textbf{effective}.  Hilbert's Nullstellensatz is not effective.  Effective versions have been given by Brownawell \cite{Brownawell87}, Koll\'ar \cite{Kollar88} and others, but their bounds are much more complicated than the ones in Theorem \ref{CN}.  \\
$\bullet$ In Theorem \ref{CN} the $\varphi_i$'s are extremely restricted.   On the other hand, in Hilbert's Nullstellensatz the $g_i$'s can be any set of polynomials.  Thus Theorem \ref{HN} is a 
\emph{full Nullstellensatz}, whereas Theorem \ref{CN} is a \emph{partial Nullstellensatz}.
\\ \\
We will promote Theorem \ref{CN} to a full Nullstellensatz  
for all finite subsets.

\subsection{The Restricted Variable Formalism}
%\textbf{} \\ \\ \noindent
%Let $F$ be any field.  The main result of this note gives a full Nullstellensatz 5for finite algebraic subsets which includes as a special case Theorem \ref{CN} for %$F$ without the upper bounds on the degree.  We supplement this with another, very %simple, result, which when combined with the main result recovers the degree %conditions of Theorem \ref{CN} (and holds over any domain $F$).
%\\ \indent
%Our main result is more general 
%than Theorem \ref{CN} in a further sense: we consider \emph{arbitrary} finite %subsets of $F^n$, not just the \emph{cylindrical} subsets $\prod_{i=1}^n X_i$. 
%% In the noncylindrical case we do not get an effective result in the above sense, %%but we believe that it ought to be possible to obtain such a result.  This seems %like an interesting open problem.  
%\\ \\
%In this section we give the formalism for a Nullstellensatz in the restricted variable %context.  Although our main theorem applies to finite subsets of affine $n$-space over %a field, it is possible to set things up more generally, and doing so raises some %further interesting questions and will be seen to have some useful applications.   
%\\ \\
%\\ \\
%Let $R$ be a ring, $n \in \Z^+$, $R[t] = R[t_1,\ldots,t_n]$, and let 
%$X \subset R^n$.
%We set up the formalism for a \textbf{restricted variable Nullstellensatz}.  
% The key observation: in Theorem \ref{CN}, the $\varphi_1,\ldots,\varphi_n$ are %chosen %to have common zero set $X = \prod_{i=1}^n X_i$, so the condition on $f \in %F[t]$ that %for all $x \in F^n$, $\varphi_1(x) = \ldots = \varphi_n(x) = 0 \implies %f(x) = 0$ is %equivalent to: for all $x \in X$, $\varphi_1(x) = \ldots = %\varphi_n(x) = 0 \implies %f(x) = 0$.  We will replace $X$ by any finite subset of %$F^n$ and replace the special %polynomials $\varphi_1,\ldots,\varphi_n$ by an %arbitrary set of polynomials.
%\\ \\
For a set $Z$, let $2^Z$ be its power set.  For a ring $R$, let $\mathcal{I}(R)$ be the set of ideals of $R$.  For a subset $J$ of a ring $R$, let $\langle J \rangle$ be the ideal of $R$ generated by $J$ and let $\rad J =  \{f \in R \mid f^k \in \langle J \rangle \text{ for some }  k \in \Z^+\}$.  An ideal $J$ is \textbf{radical} if $J = \rad J$.  
\\ \\
Let $R$ be a ring, and let $X \subset R^n$.  For $x \in X, \ f \in R[\underline{t}]$, we put 
\[ I(x) = \{f \in R[\underline{t}] \mid f(x) = 0\}, \]
\[ V_X(f) = \{ x \in X \mid f(x) = 0\}. \]
\noindent
When $R$ is an algebraically closed field and $X \subset R^n$ is Zariski-closed (c.f. $\S 4.2$), this is the usual connection between subsets of an affine variety and its coordinate ring.  We will see that the case of $R$ any field and $X$ finite is even better behaved.  In $\S 4$ we return to the general case and find some new phenomena.  
\\ \\
Put $V = V_{R^n}$.  We may extend $I$ and $V_X$ to maps on power sets as follows:
\[ I: 2^X \ra 2^{R[\underline{t}]}, \ A  \mapsto I(A) = \bigcap_{a \in A} I(a) = 
\{ f \in R[\underline{t}] \mid \forall a \in A, \ f(a) = 0\}, \]
\[ V_A: 2^{R[\underline{t}]} \ra 2^X, \ J  \mapsto V_A(J) = \bigcap_{f \in J} V_A(f) = \{ a \in A \mid \forall f \in J, \ f(a) = 0\}. \]
In fact $I(2^X) \subset \mathcal{I}(R[\underline{t}])$: $\forall J \subset R[\underline{t}], \ V(J) = V(\langle J \rangle)$.  Moreover we have 
%The maps $I$ and $V_A$ are \textbf{antitone}: 
\[A_1 \subset A_2 \subset X \implies I(A_1) \supset I(A_2), \]
\[ J_1 \subset J_2 \subset F[\underline{t}] \implies V_A(J_1) \supset V_A(J_2), \]
hence also
\[ A_1 \subset A_2 \subset X \implies V_X(I(A_1)) \subset V_X(I(A_2)), \]
\[ J_1 \subset J_2 \subset R[\underline{t}] \implies I(V_X(J_1)) \subset I(V_X(J_2)). \]
We have $X = V_X(0)$, so 
\[\forall J \subset R[\underline{t}], \ I(V_X(J)) \supset I(V_X(0)) = I(X). \] 



\subsection{The Finitesatz}

\begin{lemma}
\label{FRNALEMMA}
%a) For all $J \subset F[\underline{t}]$ and $A \subset X$, we have 
%\[ V_X(I(V_X(J)) = V_X(J), \ I(V_X(I(A)) = I(A). \]
%b) 
a) Suppose $R$ is a domain.  For all ideals $J_1,\ldots,J_m$ of $R[\underline{t}]$, we have \[V_X(J_1 \cdots J_m) = \bigcup_{i=1}^m V_X(J_i). \]
b) Suppose $R$ is reduced.  Then for all $A \subset R^n$, $I(A)$ is a radical ideal.  \\
c) If $R$ is reduced, then for all $J \subset R[\underline{t}]$, 
\begin{equation}
\label{LOWERBOUNDEQ}
I(V_X(J)) \supset \rad(J+I(X)) \supset \rad J + I(X) \supset J + I(X).
\end{equation}
\end{lemma}
\begin{proof}
%a) Since $V_X \circ I$ is isotone, we have $V_X(J) \subset V_X(I(V_X(J)))$.  
%Since $I \circ V_X$ is isotone and $V_X$ is antitone, we have $I(V_X(J)) \supset J$ %and thus $V_X(I(V_X(J))) \subset V_X(J)$.  The identity $I(V_X(I(A)) = I(A)$ is %established in exactly the same way.  \\
%b)
a) We 
%intend to allow $m = 0$, in which case the identity reads $V_X(\langle 1 \rangle) = %\varnothing$, which is true.  Having established that, we
 immediately reduce to the case $m = 2$.  Since $J_1 J_2 \subset J_i$ for $i = 1,2$, $V_X(J_1 J_2) \supset V_X(J_i)$ 
for $i = 1,2$, thus $V_X(J_1 J_2) \supset V_X(J_1) \cup V_X(J_2)$.  Now let $x \in X \setminus (V_X(J_1) \cup V_X(J_2))$.  For $i = 1,2$ there 
is $f_i \in J_i$ with $f_i(x) \neq 0$.  Since $R$ is a domain, 
$f_1(x) f_2(x) \neq 0$, so $x \notin V_X(J_1 J_2)$. \\
b) If $f \in R[\underline{t}]$ and $f^k \in I(A)$ for some $k \in \Z^+$, then for all 
$x \in A$ we have $f(x)^k = 0$.  Since $R$ is reduced, this implies $f(x) = 0$ 
for all $x \in A$ and thus $f \in I(A)$.  \\
c) $I(V_X(J)) = I(X \cap V(J))$ is a radical ideal containing both $I(X)$ and 
$I(V(J)) \supset J$, so it contains $\rad (J+I(X))$.  The other inclusions 
are immediate.  
\end{proof} 
\noindent
It is well known (see Theorem \ref{CATS}) that when $F$ is infinite we have $I(F^n) = \{0\}$.  This serves to motivate the following restatement of Hilbert's Nullstellensatz.
%\footnote{The equivalence of the two formulations uses 
%the Hilbert Basis Theorem.}

\begin{thm} 
Let $F$ be an algebraically closed field.  For all $J \subset F[\underline{t}]$, 
\[ I(V(J)) = \rad J. \]
\end{thm}
\noindent
In comparison, CNI says $I(V(\langle \varphi_1,\ldots,\varphi_n \rangle)) = 
\langle \varphi_1,\ldots,\varphi_n \rangle$.  
%\\ \\
%Here is the main result of this section.

\begin{thm}(Finitesatz)
\label{FRN}
\label{MAINTHM}
Let $F$ be a field, and let $X \subset F^n$ be a finite subset. \\  
a) For all ideals $J$ of $F[\underline{t}]$, we have 
\begin{equation}
\label{FRNAEQ}
 I(V_X(J)) =  J + I(X). 
\end{equation}
In particular, if $J \supset I(X)$ then $I(V_X(J)) = J$. \\
b) (CNI) Suppose $X = \prod_{i=1}^n X_i$ 
for finite nonempty subsets $X_i$ of $F$.  Define $\varphi_i(t_i) \in F[t_i]$ as in (\ref{DIAGONALPHIEQ}) above.   Then 
\begin{equation}
\label{IXEQ}
 I(X) = \langle \varphi_1,\ldots,\varphi_n \rangle. 
\end{equation}
%c) If $X = \prod_{i=1}^n X_i$, then
%\[ I(V_X(\langle \varphi_1,\ldots,\varphi_n \rangle)) =
%\langle \varphi_1,\ldots,\varphi_n \rangle + I(X) = I(X) + I(X) = I(X).\]
\end{thm}
\begin{proof}
a) Let $F$ be a field, and let $X \subset F^n$ be finite.  Let $x = (x_1,\ldots,x_n) \in X$.  Let $\mm_x = \langle t_1-x_1,\ldots,t_n-x_n \rangle$.  
Then $F[\underline{t}]/\mm_x \cong F$, so $\mm_x$ is maximal.  On the other hand $\mm_x \subset I(x) \subsetneq F[\underline{t}]$, so $\mm_x = I(x)$.  Moreover 
$V_X(\mm_x) = \{x\}$, hence 
\[ I(V_X(\mm_x)) = I(x) = \mm_x. \]
Now let $A = \{a_i\}_{i=1}^k \subset X$ with $a_i \neq a_j$ for $i \neq j$.  Then
\[ I(A) = I(\bigcup_i \{a_i\}) = \bigcap_i I(a_i) = \bigcap_i \mm_{a_i}, \]
so by the Chinese Remainder Theorem \cite[Cor. 2.2]{Lang},
\[ F[\underline{t}]/I(A) = F[\underline{t}]/\bigcap_i \mm_{a_i} \cong \prod_i F[\underline{t}]/\mm_{a_i} \cong F^{\# A}. \]
Let $F^A$ be the set of all maps $f: A \ra F$, so $F^A$ is an $F$-algebra under pointwise addition and multiplication and $F^A \cong \prod_{i=1}^{\# A} F$.   The \textbf{evaluation map}
\[E_A = F[\underline{t}] \ra F^A, \ f \in F[\underline{t}] \mapsto (x \in A \mapsto f(x)) \]
is a homomorphism of $F$-algebras.  Moreover $\Ker E_A = I(A)$, so $E_A$ 
induces a map 
\[ \iota: F[\underline{t}]/I(A) \hookrightarrow F^A. \]
Thus $\iota$ is an injective $F$-linear map between $F$-vector spaces of equal finite 
dimension, hence it an is an isomorphism of rings.  It follows that
\[ \# \mathcal{I}(F[\underline{t}]/I(X)) = \# \mathcal{I}(F^X) = 2^{\# X}. \]  
Identifying $I(F[\underline{t}]/I(X))$ with $\{J \in I(F[\underline{t}]) \mid J \supset I(X)\}$ and restricting $V_X$ to ideals containing $I(X)$, we get maps
\[ V_X: \mathcal{I}(F[\underline{t}]/I(X)) \ra 2^X, \ J \mapsto V_X(J) \]
\[ I: 2^X \ra \mathcal{I}(F[\underline{t}]/I(X)), A \mapsto I(A). \]
For all $A \subset X$, 
\[ V_X(I(A)) = V_X(\prod_{i=1}^k \mm_{a_i}) = \bigcup_{i=1}^k V_X(\mm_{a_i}) = \bigcup_{i=1}^k \{a_i\} =  A. \]
Since $\mathcal{I}(F[\underline{t}]/I(X))$ and $2^X$ have the same finite cardinality, 
it follows that $V_X$and $I$ are mutually inverse bijections!  Thus for any 
ideal $J$ of $F[\underline{t}]$, using (\ref{LOWERBOUNDEQ}) we get
\[ J+I(X) \subset I(V_X(J)) \subset I(V_X(J+I(X))) = J + I(X). \]
b) Let $d_i = \deg \varphi_i$ and put $\Phi = \langle \varphi_1,\ldots,\varphi_n \rangle$.  Since $\varphi_i|_X \equiv 0$ for all $i$, we get $\Phi \subset \Ker E_X$, and thus there is an induced surjective $F$-algebra homomorphism 
\[ \tilde{E}_X: F[\underline{t}]/\Phi \ra F[\underline{t}]/\Ker E_X \ra F^X. \]
Since $F[\underline{t}]/\Phi$ and $F^X$ are $F$-vector spaces of dimension $d_1 \cdots d_n$,  $\tilde{E}_X$ is an isomorphism.  Hence $F[\underline{t}]/\Phi \ra 
F[\underline{t}]/\Ker E_X$ is injective, i.e., $\Phi = \Ker E_X = I(X)$.  
\end{proof}



%\begin{remark}
%From Theorem \ref{FRN} we deduce the Combinatorial Nullstellensatz I:
%\[ I(V_X(\langle \varphi_1,\ldots,\varphi_n \rangle)) =
%\langle \varphi_1,\ldots,\varphi_n \rangle + I(X) = I(X) + I(X) = I(X).\]
%This is the Combinatorial Nullstellensatz I without the degree conditions.
%\end{remark}


\begin{cor}(Finite Field Nullstellensatz \cite{Terjanian66})
\label{FFN}
Let $\F_q$ be a finite field.  Then for all ideals $J$ of $\F_q[t]$, we have $I(V_{\F_q^n}(J)) = J + \langle t_1^q-t_1,\ldots,t_n^q-t_n \rangle$.
\end{cor}
\begin{proof}
Apply Theorem \ref{FRN} with $F = X_1 = \ldots = X_n = \F_q$.
\end{proof}


\section{Cylindrical Reduction, the Atomic Formula, and the Nullstellens\"atze}


\subsection{Cylindrical Reduction}
%\textbf{} \\ \\ \noindent
%Let $F$ be a domain, and let $X \subset F^n$ be any nonempty subset.  
%As above, polynomials induce $F$-valued functions on $X$, giving 
%an evaluation map
%\[ E_X: F[\underline{t}] \ra X^F, \ f \in F[\underline{t}] \mapsto (x \in X \mapsto f(x)). \]
%%Let $\mathcal{P}_X = E_X(F[\underline{t}])$, the \textbf{polynomial functions on X}.
%The Combinatorial Nullstellens\"atze are easy and familiar when $n = 1$: both %amount to nothing else than the \textbf{Root-Factor Theorem}: 
%for a univariate polynomial $f(t)$ over a field (or even a domain) and 
%$a \in F$, we have $f(a) = 0$ iff $(t-a) \mid f$.  
%\\ \\
%For $n \geq 1$, these arguments have direct analogues in the \textbf{cylindrical %case}: 
%Let $X = \prod_{i=1}^n X_i$ for $X_1,\ldots,X_n \subset F$.  We now reestablish 
%the key equality $I(X) = \langle \varphi_1,\ldots,\varphi_n \rangle$ of CNI = 
%Theorem \ref{FRN}b) in a different and in some ways superior manner: e.g. with 
%suitable care we can treat the case of an arbitrary ring of coefficients.
 
\begin{lemma}(Polynomial Division)
\label{POLDIV} \\
Let $R$ be a ring, and let $a(t_1),b(t_1) \in R[t_1]$ with $b$ monic of degree $d$. \\
a) There are unique polynomials $q$ and $r$ with $a = qb + r$ and $\deg r < d$.  \\
b) Suppose $R = A[t_2,\ldots,t_n]$ is itself a polynomial ring over a ring $A$, so $R[t_1] = A[t_1,\ldots,t_n] = A[t]$ and that $b \in A[t_1]$.  Then: \\
$\bullet$ If $q$ has a monomial term 
of multidegree $(d_1,\ldots,d_n)$, then $a$ has a monomial term of 
multidegree $(d_1+d,d_2,\ldots,d_n)$.  It follows that 
\[\deg a \leq \deg q + d. \]
$\bullet$ If $r$ has a monomial term of multidegree $(d_1,\ldots,d_n)$, 
then $a$ has a monomial term of multidegree $(e_1,\ldots,e_n)$ with $d_i \leq e_i$ for all $1 \leq i \leq n$.   It follows that 
\[ \deg r \leq \deg a. \]
\end{lemma}
\begin{proof}
a) Uniqueness: if $a = q_1 b + r_1 = q_2 b + r_2$, then since $b$ is monic and $g_1 \neq g_2$ then we have $d \leq \deg((g_1-g_2)b) = \deg (r_2 - r_1) 
< d$, a contradiction.  Existence: when $b$ is monic, the standard division algorithm involves no division of coefficients so works in any ring.  Part b) follows by contemplating the division algorithm.
\end{proof} 


\begin{prop}(Cylindrical Reduction)
\label{CYLINDRICALREDUCTION}
Let $R$ be a ring.  For $1 \leq i \leq n$, let $\varphi_i(t_i) \in F[t_i]$ be monic of degree $c_i$.  Put $\Phi = \langle \varphi_1,\ldots,\varphi_n \rangle$ and $\cc = (c_1,\ldots,c_n)$.  We say $f \in R[\underline{t}]$ is \textbf{$\cc$-reduced} if for all $1 \leq i \leq n$, $\deg_{t_i} f < c_i$.  Then: \\
a) The set $\mathcal{R}_{\cc}$ of all $\cc$-reduced polynomials is a free $R$-module of rank $c_1 \cdots c_n$.  \\
b) For all $f \in R[\underline{t}]$, there are $q_1,\ldots,q_n \in R[\underline{t}]$ such that $\deg q_i \leq 
\deg f - \deg \varphi_i$ for all $1 \leq i \leq n$ and $f-\sum_{i=1}^n q_i \varphi_i$ is $\cc$-reduced.  \\
c) The composite map $\Psi: \mathcal{R}_{\cc} \hookrightarrow R[\underline{t}] \ra R[\underline{t}]/\Phi$ is an $R$-module isomorphism.  \\
d) For all $f \in R[\underline{t}]$, there is a unique $r_{\cc}(f) \in \mathcal{R}_{\cc}$ such that 
$f-r_{\cc}(f) \in \Phi$.
% \\
%e) If $f \in \Phi$, then $f = \sum_{i=1}^n q_i \varphi_i$ with $\deg q_i \leq \deg %f - \deg \varphi_i$ for all $1 \leq i \leq n$.  
%\\
%c) The map $f \mapsto \overline{f}$ induces 
%an isomorphism of $k$-modules \[R[\underline{t}]/\langle \varphi_1,\ldots,\varphi_n \rangle %\stackrel{\sim}{\ra} \mathcal{R}_{\dd}. \]
\end{prop}
\begin{proof}
a) Indeed $\{t_1^{a_1} \cdots t_n^{a_n} \mid 0 \leq a_i < d_i\}$ is a basis for $\mathcal{R}_{\cc}$. \\
b) Divide $f$ by $\varphi_1$, then divide 
the remainder $r_1$ by $\varphi_2$, then divide the remainder $r_2$ by $\varphi_n$, and so forth, getting $f = \sum_{i=1}^n q_i \varphi_i + r_n$.  Apply 
Lemma \ref{POLDIV}b).  \\
c) Part b) implies that $\Psi$ is surjective.  For the injectivity: let 
$q_1,\ldots,q_n \in R[\underline{t}]$ be such that $f = \sum_{i=1}^n q_i \varphi_i \in \mathcal{R}_{\cc}$.  We must show that $f = 0$.  For each $i$, by dividing $q_i$ 
by $\varphi_j$ for $i < j \leq n$ and absorbing the quotient into the 
coefficient $q_j$ of $\varphi_j$, we may assume that $\deg_{t_j} q_i < d_j$ 
for all $j > i$.  It follows inductively that for all $1 \leq m \leq n$, 
$\sum_{i=1}^m q_i \varphi_i$ is either $0$ or has $t_i$-degree at least 
$d_i$ for some $1 \leq i \leq m$.  Applying this with $m = n$ shows $f = 0$.  d) This follows from part c).  
\end{proof}
\noindent
Let $R$ be a ring and $X_1,\ldots,X_n \subset R$ be finite, nonempty subsets.  Put $\varphi_i = \prod_{x_i \in X_i} (t_i-x_i)$, $\Phi = \langle \varphi_1,\ldots,\varphi_n \rangle$, $d_i = \# X_i-1$, $\dd = (d_1,\ldots,d_n)$ and $X = \prod_{i=1}^n X_i$.  A polynomial $f \in R[\underline{t}]$ is \textbf{$X$-reduced} if it is 
$(\# X_1,\ldots,\# X_n)$-reduced.  We write $\mathcal{R}_X$ for $\mathcal{R}_{\dd}$, so $\dim \mathcal{R}_{X} = \prod_{i=1}^n \left(d_i+1\right) = \# X$.  The 
\textbf{$X$-reduced representative} of $f$ is the unique polynomial $r_X(f)$ 
such that $f-r_X(f) \in \Phi$.   

\begin{definition}
Let $R$ be a ring and $n \in \Z^+$.  A subset $S \subset R$ 
satisfies \textbf{Condition (F)} (resp. \textbf{Condition (D)}) if for all $x \neq y \in S$, $x-y \in R^{\times}$ (resp. $x-y$ is not a zero-divisor in $R$: if $(x-y)z = 0$ then $z = 0$).  We say $X = \prod_{i=1}^n X_i \subset R^n$ satisfies \textbf{Condition (F)} (resp. 
\textbf{Condition (D)}) if 
every $X_i$ does. 
% A subset $S \subset R$ satsfies \textbf{Condition (D)} if 
%for all $x \neq y \in S$, $x-y$ is not a zero-divisor in $R$: if $(x-y)z = 0$ then 
%$z = 0$. A subset $X = \prod_{i=1}^n X_i \subset R^n$ satisfies \textbf{Condition %(D)} 
%if every $X_i$ does.
\end{definition}
\noindent
Condition (F) implies Condition (D).  Conversely, Condition (D) implies Condition (F) 
with $R$ replaced by its total fraction ring.  A ring is a field (resp. a domain) 
iff every subset satisfies Condition (F) (resp. Condition (D)).  



\begin{thm}(\textbf{CATS Lemma} \cite{Chevalley35} \cite{Alon-Tarsi92}, \cite{Schauz08a})
\label{CATLEMMA}
\label{CATS}
Let $R$ be a ring.  For $1 \leq i \leq n$, let $X_i \subset R$ be nonempty and finite.  Put $X = \prod_{i=1}^n X_i$. \\
a) (Schauz) The following are equivalent: \\
(i) $X$ satisfies condition (D). \\
(ii) If $f \in \mathcal{R}_X$ and $f(x) = 0$ for all $x \in X$, then $f = 0$. \\
(iii) We have $\Phi = I(X)$.  \\
b) (Chevalley-Alon-Tarsi) The above conditions hold when $R$ is a domain.
\end{thm}
\begin{proof}
a) (i) $\implies$ (ii): By induction on $n$: suppose $n = 1$.  Write 
$X = \{x_1,\ldots,x_{a_1}\}$, and let $f \in R[t_1]$ have degree less than 
$a_1-1$ such that $f(x_i) = 0$ for all $1 \leq i \leq a_1$.  By Polynomial 
Division, we can write $f = (t_1-x_1)f_2$ for $f_2 \in R[t_1]$.  Since $x_2-x_1$ is not a zero-divisor, 
$f_2(x_2) = 0$, so $f_2(t_1) = (t_1-x_2)$.  Proceeding in this manner we eventually get $f(t_1) = (t_1-x_1) \cdots (t_1 - x_{a_1}) f_{a_1+1}(t_1)$, and comparing 
degrees shows $f = 0$.  Suppose $n \geq 2$ and that the result holds in $n-1$ variables.  Write
\[ f= \sum_{i=0}^{a_n-1} f_i(t_1,\ldots,t_{n-1}) t_n^i\]
with $f_i \in R[t_1,\ldots,t_{n-1}]$.  If $(x_1,\ldots,x_{n-1}) \in \prod_{i=1}^{n-1} X_i$, then $f(x_1,\ldots,x_{n-1},t_n) \in R[t_n]$ has degree less than $a_n$ and vanishes for all $a_n$ elements $x_n \in X_n$, so it is the zero polynomial: $f_i(x_1,\ldots,x_{n-1}) = 0$ for all $0 \leq i \leq a_n$.  By induction, each $f_i(t_1,\ldots,t_{n-1})$ is the zero polynomial and thus $f$ is the zero polynomial. \\
(ii) $\implies$ (iii):  We have $\Phi \subset I(X)$.  Let $f \in I(X)$.  
Since $f-r_X(f) \in \Phi \subset I(X)$, for all $x \in X$ we have 
$r_X(f)(x) = f(x) = 0$.  Then (ii) gives $r_X(f) = 0$, so $f \in \Phi$. \\
(iii) $\implies$ (i): We argue by contraposition: suppose $X$ does not 
satisfy Condition (D).  Then for some $1 \leq i \leq n$, we may write 
$X_i = \{x_1,x_2,\ldots,x_{a_i}\}$ such that there is $0 \neq z \in R$ 
with $(x_1-x_2)z = 0$.  Then $f = z(t_i-x_2)(t_i-x_3) \cdots (t_i-x_{a_i})$
is a nonzero element of $I(X) \cap \mathcal{R}_X$, hence 
$f \in I(X) \setminus \Phi$.  \\
b) If $R$ is a domain then Condition (D) holds for every $X$.  
\end{proof}

%\begin{thm}
%Let $F$ be a domain.  For $1 \leq i \leq n$, let $X_i$ be a nonempty finite subset %of $F$.  Put $X = \prod_{i=1}^n X_i$. \\
%a) (Chevalley-Alon-Tarsi Lemma) If $f \in \mathcal{R}_X$ and $f|_X \equiv 0$, then %$f = 0$.  \\
%b) We have $\Phi = I(X)$.
%\end{thm}
%\begin{proof}
%a) We should begin by pointing out that this result appears in \cite{Alon-Tarsi92} 
%in full generality and in \cite{Chevalley35} (in the case $X_1 = \ldots = X_n = F = %\F_q$, but the proof works in general): this argument is by induction, and it takes %about $10$ lines. \\ \indent
%Alternately: by 
%replacing $F$ with its fraction field we reduce to the case of a field.  By the %proof of Theorem \ref{FRN}a), $E_X: F[\underline{t}] \ra F^X$ is surjective.  Since 
%$f - r_X(f) \in \Phi \subset I(X) = \Ker E_X$, we have that $E_X|_{\mathcal{R}_X}: 
%\mathcal{R}_X \ra F^X$ is a surjective linear map between $F$-vector spaces 
%of equal finite dimension, so it is also injective.  \\
%b) As above, certainly $\Phi \subset I(X)$.  Now let $f \in I(X)$.  
%Since $f-r_X(f) \in \Phi \subset I(X)$, for all $x \in X$ we have 
%$r_X(f) = f(x) = 0$.  By part a), $r_X(f) = 0$ and thus $f \in \Phi$.  
%\end{proof}
%\noindent
%Suppose $F$ is a domain and $f \in F[\underline{t}]$ vanishes on $X$.  By Theorem \ref{CATLEMMA} %$f \in \Phi$, and thus by Proposition \ref{CYLINDRICALREDUCTION} there are %$q_1,\ldots,q_n \in F[\underline{t}]$ with $\deg q_i \leq \deg f - a_i$ for 
%all $i$ such that $f-\sum_{i=1}^n q_i \varphi_i = r_X(f) = 0$, so 
%$f = \sum_{i=1}^n q_i \varphi_i$.  This proves Theorem \ref{CN}b).


\subsection{The Atomic Formula}
%\textbf{} \\ \\ \noindent
%We maintain the setup of the previous section.  Moreover, we say $X = \prod_{i=1}^n %X_i$ satisfies \textbf{Condition (F)} if for all $1 \leq i \leq n$ and all $x_i %\neq y_i \in X_i$, $x_i -y_i \in F^{\times}$.  

%\begin{remark}
%a) Condition (F) holds for all $X$ iff $F$ is a field.  \\
%b) Condition (F) holds if for all $i$, $\# X_i = \{1\}$ or $X_i = \{x,x+1\}$.  
%The converse is true when $F = \Z$. \\
%c) If Condition (F)  holds, then for all $i$, $\# X_i \leq \# R^{\times} + 1$.  \\ 
%\end{remark}

\begin{lemma}
Suppose Condition (F).  Let $x = (x_1,\ldots,x_n) \in X$, and put
\[\delta_{X,x} = \prod_{i=1}^n \prod_{y_i \in X_i \setminus \{x_i\}} 
\frac{t_i-y_i}{x_i-y_i} = \prod_{i=1}^n 
\frac{\varphi_i(t_i)}{(t_i-x_i)\varphi_i'(x_i)}
\in F[\underline{t}]. \]
a) We have $\delta_{X,x}(x) = 1$.  \\
b) If $y \in X \setminus \{x\}$, then $\delta_{X,x}(y) = 0$.  \\
c) For all $1 \leq i \leq n$, $\deg_{t_i} \delta_{X,x} = a_i -1$.  In particular, $\delta_{X,x}$ is $X$-reduced. 
\end{lemma}
\begin{proof} Left to the reader.
\end{proof}
\noindent
The following is a result of U. Schauz \cite[Thm. 2.5]{Schauz08a}.  

\begin{thm}(Atomic Formula) Suppose Condition (F).  Then for all $f \in R[\underline{t}]$, we have  
\begin{equation}
\label{ATOMICDECOMPOSITION}
r_X(f) = \sum_{x \in X} f(x) \delta_{X,x}.
\end{equation}
\end{thm}
\begin{proof} 
Apply Theorem \ref{CATLEMMA}a) to $r_X(f) - \sum_{x \in X} f(x) \delta_{X,x}$.
%the difference of the two sides of (\ref{ATOMICDECOMPOSITION}).
%The two sides of (\ref{ATOMICDECOMPOSITION})
%Both sides are $X$-reduced and induce the same function on $X$.
%Both sides are $X$-reduced and give the same function on $X$  Apply Lemma %\ref{CATLEMMA}.
\end{proof}
%\begin{remark}
%When $n = 1$, (\ref{ATOMICDECOMPOSITION}) is the \textbf{Lagrange Interpolation %Formula}.   
%\end{remark}
\noindent
Let $\cc = (c_1,\ldots,c_n) \in \N^n$.  We say a polynomial $f \in F[\underline{t}]$ is 
\textbf{$\cc$-topped} if for every $e = (e_1,\ldots,e_n)$ with $\cc < \ee$, 
the coefficient of $t^{\ee} = t_1^{e_1} \cdots t_n^{e_n}$ in $f$ is $0$.
%  If 
%$\deg f \leq c_1 + \ldots + c_n$, then $f$ is $\cc$-topped.


\begin{remark}
\label{DEGREEDTOPPED}
Let $\cc = (c_1,\ldots,c_n) \in \N^n$.  If $\deg f \leq c_1 + \ldots + c_n$, then $f$ is $\cc$-topped.  
\end{remark}


\begin{lemma}
\label{TOPPEDLEMMA}
Let $f \in R[\underline{t}]$ be $\dd$-topped.  
 Then the coefficient of $t^{\dd} = t_1^{d_1} \cdots t_n^{d_n}$ in $f$ is 
equal to the coefficient of $t^{\dd}$ in $r_X(f)$.   
\end{lemma}
\begin{proof}
Write $\varphi_i(t_i)= t_i^{d_i+1} - \psi_i(t_i)$, $\deg(\psi_i) \leq d_i$.  An \textbf{elementary reduction} of $f$ consists of identifying a monomial which is divisible by $t_i^{d_i+1}$ and replacing $t_i^{d_i+1}$ by $\psi_i(t_i)$.  
Elementary reduction on a $\dd$-topped polynomial 
yields a $\dd$-topped polynomial with the same coefficient of $t^{\dd}$.  We obtain $r_X(f)$ from $f$ by finitely many elementary reductions.
%Suppose $f$ is $d$-topped and $g$ is obtained from $f$ by 
%performing an elementary cylindrical reduction.  Then $g$ is still $d$-topped.  %Moreover, if the coefficient of $t^d$ in $g$ 
%were different from the coefficient of $t^d$ in $f$, the reduction was 
%done on a monomial $m = c_r t_1^{r_1} \cdots t_n^{r_n}$ such that $r_i = a_1-1$ 
%for all but exactly one index $i$, say $i_0$.  But then by definition of %$d$-topped, we must have $r_{i_0} \leq a_{i_0} - 1$ and thus the monomial $m$ is 
%already cylindrically reduced, contradiction.  Since $r(f)$ 
%is obtained from $f$ by finitely many elementary cylindrical reductions, 
%the result follows.
\end{proof}
%\noindent
%We deduce a \emph{proof} of the Coefficient Formula (Theorem \ref{COEFFTHM}): by Remark %\ref{DEGREEDTOPPED}, $f$ is $d$-topped, so 
%$c_{\dd}(f) = c_{\dd}(r_X(f))$.   Apply (\ref{ATOMICDECOMPOSITION}).  


%\begin{remark}
%The proof shows that Theorem \ref{COEFFTHM} holds with weaker hypotheses: \\
%(i) ``$\deg f \leq a_1 + \ldots + a_n$'' can be weakened to ``$f$ is %$(a_1,\ldots,a_n)$-topped''.  \\
%(ii)  ``$F$ is a field'' can be weakened to ``$S$ satisfies Condition (F)''.  It can be %further weakened to ``$S$ satisfies 
%Condition (D)'' so long as we interpret (\ref{COEFF}) as taking place 
%in the total fraction ring of $F$ (equivalently, if we clear denominators).  \\
%The first strengthening appears in the work of Schauz and Las\'on and 
%the second appears in the work of Schauz (see especially \cite[Thm. 2.9]{Schauz08a}).  
%\end{remark}

%\begin{thm}(Coefficient Formula \cite[Thm. 3.2]{Schauz08a}, \cite[Thm. 3]{Lason10}, %\cite[Thm. 4]{Karasev-Petrov12} )
%\label{COEFFTHM}
%Let $F$ be a field.  For $1 \leq i \leq n$, let $X_i$ be a finite nonempty subset %of $F$ with $\# X_i = a_i$; put $X = \prod_{i=1}^n X_i$ and 
%$d = (a_1-1,\ldots,a_n-1)$.  Let $f \in
%F[\underline{t}]$ be $d$-topped -- recall this occurs if $\deg d < \sum_{i=1}^n (a_i-1)$ -- and %let $c_{\dd}$ be the coefficient of $t_1^{a_1-1} \cdots t_n^{a_n-1}$ in $f$.  Then
%\begin{equation}
%\label{COEFF}
% c_{\dd} = \sum_{x = (x_1,\ldots,x_n) \in X} \frac{f(x)}{\prod_{i=1}^n 
%\varphi_i'(x_i)}.
%%\prod_{y_i \in X_i \setminus \{x_i\}} (x_i-y_i)}. 
%\end{equation}
%\end{thm}
%\begin{proof}
%By Lemma \ref{TOPPEDLEMMA}, $c_{\dd}(f) = c_{\dd}(r_f)$.  Apply the Atomic Decomposition %(\ref{ATOMICDECOMPOSITION}).
%\end{proof}


\subsection{Combinatorial Nullstellens\"atze Over Rings}
%\textbf{} \\ \\ \noindent
The following result sharpens \cite[Thm. 3]{KMR12}. 
%Let $R$ be a (commutative, as always) ring, $X_1,\ldots,X_n$ be finite nonempty 
%subsets of $R$, and put $d_i = \# X_i-1$.  Put $d = (d_1,\ldots,d_n)$ and $X = %\prod_{i=1}^n X_i$.  We will deduce from the results of the previous section that the %Combinatorial Nullstellens\"atz I and the Coefficient Formula hold verbatim over $R$, %so long as $X$ satisfies Condition (D) (which is automatic if $R$ is a domain); the %latter is a result of U. Schauz.  Schauz's Coefficient Formula immediately 
%implies the Combinatorial Nullstellensatz II.  In fact, we give an ``integral version'' %of the Coefficient Formula which does not assume Condition (D): namely a formula for a %multiple of $c_d$ by an element $M(X)$ of $R$ defined in terms of $X$ and which is not %a zero-divisor iff Condition (D) holds.  In the absence of Condition (D) the %information obtained on $c_d$ is therefore incomplete, but we are still getting some %information as long as $M(X) \neq 0$.

%We make some remarks concerning these generalizations 
%generalization.
%\\ \\
%$\bullet$ It costs nothing extra.  We have isolated the hypotheses under which %the standard arguments go through essentially verbatim. 
%\\ \\
%$\bullet$ It has important applications in number theory and combinatorics.  
%\\ \\
%$\bullet$ It raises a key question: what happens 
%when Condition (D) does not hold? 

\begin{thm}
\label{CNIRING}
Let $R$ be a ring, let $X_1,\ldots,X_n \subset R$ be finite nonempty subsets, and define 
$\dd$, $X$, $\varphi_1,\ldots,\varphi_n,\Phi$ as above.
% let $X_1,\ldots,X_n \subset R$ be nonempty and finite, and $X = \prod_{i=1}^n X_i$.  %For $1 \leq i \leq n$, put
%\begin{equation}
%\label{DIAGONALPHIEQ}
% \varphi_i(t_i) = \prod_{x_i \in X_i} (t_i-x_i) \in R[t_i] \subset R[\underline{t}] = %R[t_1,\ldots,t_n].
%\end{equation}
Suppose $f \in I(X)$: i.e., $f(x) = 0$ for all $x \in X$. Then: \\
a) (Combinatorial Nullstellensatz I) The following are equivalent: \\
(i) $X$ satisfies Condition (D).  \\
(ii)  We have $f \in \Phi$: there are  $q_1,\ldots,q_n \in R[\underline{t}]$ such that $f(t) = \sum_{i=1}^n q_i(t) \varphi_i(t)$. \\
b) (Supplementary Relations) Suppose the equivalent conditions of part a) hold.  Let $\mathfrak{r}$ be the subring of $R$ generated by the coefficients of $f$ and $\varphi_1,\ldots,\varphi_n$.  We can take $q_1,\ldots,q_n \in \mathfrak{r}[t]$ and satisfying $\deg q_i \leq \deg f - \deg \varphi_i$ for all $1 \leq i \leq n$.
\end{thm}
\begin{proof} 
If $X$ satisfies Condition (D): replace $R$ by $\mathfrak{r}$ and apply Proposition \ref{CYLINDRICALREDUCTION}b) and Theorem \ref{CATS}: we get $q_1,\ldots,q_n \in \mathfrak{r}[t]$ 
such that $f = \sum_{i=1}^n q_i \varphi_i$ and $\deg q_i \leq \deg f - \deg \varphi_i$ for all $1 \leq i \leq r$.  If $X$ does not satisfy Condition (D): by Theorem \ref{CATS}, there is a nonzero element $f \in \mathcal{R}_X \cap I(X)$, and by Proposition \ref{CYLINDRICALREDUCTION}c), $f \notin \Phi$. 
\end{proof}


%\begin{remark}
%In the language of the previous section, Theorem \ref{CNIRING} shows that 
%when Condition (D) does not hold, we have $I(X) \supsetneq \langle %\varphi_1,\ldots,\varphi_n \rangle$.  In this case, it would be interesting to give a %description of $I(X)$ and also to ``bound the difference'' between 
%$I(X)$ and $\langle \varphi_1,\ldots,\varphi_n \rangle$.
%\end{remark}
\noindent
We put \[M(X) = \prod_{i=1}^n \prod_{x_i \in X_i} \prod_{y_i \in X_i \setminus \{x_i\}} 
(x_i-y_i) = \prod_{i=1}^n \prod_{x_i \in X_i} \varphi_i'(x_i). \] Thus $M(X)$ is \emph{not} a zero-divisor in $R$ iff $X$ satisfies Condition (D).  For all $x \in X$, $\prod_{i=1}^n \varphi_i'(x_i)$ is a subproduct of $M(X)$, and we denote by $\frac{M(X)}{\prod_{i=1}^n \varphi_i'(x_i)}$ the product $M(X)$ with the corresponding factors removed.  
\\ \\
For a polynomial $g \in R[\underline{t}]$, let $c_{\dd}(g)$ be the coefficient of $t^{\dd} = t_1^{d_1} \cdots t_n^{d_n}$ in $g$. 



\begin{thm}
\label{GENCOEFFTHM}
Let $R$ be a ring, let $X_1,\ldots,X_n \subset R$ be finite nonempty subsets, and define 
$\dd$, $X$, $\varphi_1,\ldots,\varphi_n,\Phi$ as above.
Let $f \in R[t_1,\ldots,t_n]$. \\
a) (\cite[Thm. 2.9]{Schauz08a}) Suppose $X$ satisfies Condition (D).  Then in the total 
fraction ring of $R$ we have
\begin{equation}
\label{GENCOEFFB}
 c_{\dd}(r_X(f)) = \sum_{x = (x_1,\ldots,x_n) \in X} \frac{f(x)}{\prod_{i=1}^n \varphi_i'(x_i)}.
\end{equation}
The right hand side of (\ref{GENCOEFFB}) lies in $R$ if $X$ satisfies Condition (F).  \\
b) (Integral Coefficient Formula) In general, we have
\begin{equation}
\label{GENCOEFFA}
 M(X) c_{\dd}(r_X(f)) = \sum_{x = (x_1,\ldots,x_n) \in X} \left( \frac{M(X)}{\prod_{i=1}^n \varphi_i'(x_i)} \right) f(x).
\end{equation}
 c) (CNII) Suppose $X$ satisfies Condition (D).  If $f \in I(X)$, then $c_{\dd}(r_X(f)) = 0$. \\
d) If $f$ is $\dd$-topped -- e.g. if $\deg f \leq \sum_{i=1}^n d_i$ -- then
$c_{\dd}(f) = c_{\dd}(r_X(f))$.  
\end{thm}
\begin{proof}
a) Replace $R$ by its total fraction ring and apply (\ref{ATOMICDECOMPOSITION}). \\
%By part a), (\ref{GENCOEFFA}) holds whenever $X$ satisfies Condition (D), so 
%certainly if $R$ is a domain.  We will deduce the general case using ``the permanence %of algebraic identities''. 
b) There is a domain $\tilde{R}$ and a surjective ring homomorphism $q: \tilde{R} \ra R$: for instance let $\tilde{R}$ be a polynomial ring over $\Z$ in a set of indeterminates $\{T_r\}_{r \in R}$ indexed by the elements of $R$ and let $q$ be the unique homomorphism with $q(T_r) = r$.  There is a unique extension of $q$ to a ring homomorphism $q: \tilde{R}[t_1,\ldots,t_n] \ra 
R[t_1,\ldots,t_n]$ with $\tilde{q}(t_i) = t_i$ for all $1 \leq i \leq n$.  
For $1 \leq i \leq n$, choose $\tilde{X}_i \subset \tilde{R}$ such that 
$q|_{\tilde{X}_i}: \tilde{X}_i \ra X_i$ is a bijection, and put $\tilde{X} = \prod_{i=1}^n \tilde{X}_i$.  Choose $\tilde{f} \in \tilde{R}[t_1,\ldots,t_n]$ such that $q(\tilde{f}) = f$.  Applying part a) and multiplying through by $M(\tilde{X})$ gives
\begin{equation}
\label{INTEGRALCOEQ1} 
 M(\tilde{X}) c_{\dd}(r_X(\tilde{f})) = \sum_{\tilde{x}  \in \tilde{X}} \left( \frac{M(\tilde{X})}{\prod_{i=1}^n \varphi_i'(\tilde{x}_i)} \right) f(\tilde{x}). 
\end{equation}
Applying $q$ to both sides of (\ref{INTEGRALCOEQ1}) gives 
\[ M(X) c_{\dd}(q(r_{\tilde{X}}(\tilde{f}))) = \sum_{x \in X} \left( \frac{M(X)}{\prod_{i=1}^n \varphi_i'(x_i)} \right) f(x). \]
Applying $q$ to $\tilde{f} - r_{\tilde{X}}(\tilde{f}) \in \tilde{\Phi}$ gives 
$f-q(r_{\tilde{X}}(\tilde{f})) \in \Phi$.  Since $q(r_{\tilde{X}}(\tilde{f}))$ is $X$-reduced, Proposition \ref{CYLINDRICALREDUCTION}d) implies
\[ q(r_{\tilde{X}}(\tilde{f})) = r_X(f). \]
%Let $\tilde{f}(t_1,\ldots,t_n) = \sum \tilde{c}_I t^I$ be a \emph{generic polynomial}: %$\tilde{f} \in \tilde{R}[t]$, where $\tilde{R} = \Z[ \{\tilde{c}_I\}, \tilde{x}_{i,j}]$ %is a polynomial ring over $\Z$ with independent indeterminates $\tilde{c}_I$ for each %$I \in \N^n$ such that 
%the corresponding coefficient $c_I$ of $f$ is nonzero, and $\tilde{x}_{i,j}$ 
%for all $1 \leq i \leq n$ and $1 \leq j \leq d_i+1$.  For $1 \leq i \leq n$, 
%put $\tilde{X}_i = \{ \tilde{x}_{i,j}\}_{1 \leq j \leq d_i+1}$ and 
%$\tilde{X} = \prod_{i=1}^n \tilde{X}_i$.  Since $f$ is $\dd$-topped and $\tilde{c}_I \neq %0$ 
%iff $c_I \neq 0$, $\tilde{f}$ is $d$-topped.  Since $\tilde{R}$ is a 
%domain, by Step 1 (\ref{GENCOEFFB}) and thus also (\ref{GENCOEFFA}) holds for %$\tilde{f}$ and $\tilde{X}$.   Mapping each $\tilde{c}_I$ to $c_i \in R$ and each %$\tilde{x}_{i,j}$ to $x_{i,j} \in X_i \subset R$ gives a ring homomorphism $\tilde{R} %\ra R$, and 
%thus (\ref{GENCOEFFA}) holds for $f$ and $X$.  \\
c) This follows from part a).  d)  This is Lemma \ref{TOPPEDLEMMA}.
\end{proof}



%\begin{remark}
%\label{CFMREM}
%Theorem \ref{COEFFTHM} holds with weaker hypotheses: \\
%(i) ``$\deg f \leq a_1 + \ldots + a_n$'' can be weakened to ``$f$ is 5$(a_1,\ldots,a_n)$-topped''.  \\
%(ii)  ``$F$ is a field'' can be weakened to ``$S$ satisfies Condition (F)''.  %It can be further weakened to ``$S$ satisfies 
%Condition (D)'' so long as we interpret (\ref{COEFF}) as taking place 
%in the total fraction ring of $F$ (equivalently, if we clear denominators).  \\
%The first strengthening appears in the work of Schauz and Las\'on and 
%the second appears in the work of Schauz (see especially \cite[Thm. %2.9]{Schauz08a}).  
%\end{remark}

%\begin{thm}(Coefficient Formula \cite[Thm. 3.2]{Schauz08a}, \cite[Thm. 3]{Lason10}, %\cite[Thm. 4]{Karasev-Petrov12} )
%\label{COEFFTHM}
%Let $F$ be a field.  For $1 \leq i \leq n$, let $X_i$ be a finite nonempty subset %of $F$ with $\# X_i = a_i$; put $X = \prod_{i=1}^n X_i$ and 
%$d = (a_1-1,\ldots,a_n-1)$.  Let $f \in
%F[\underline{t}]$ be $d$-topped -- recall this occurs if $\deg d < \sum_{i=1}^n (a_i-1)$ -- and %let $c_d$ be the coefficient of $t_1^{a_1-1} \cdots t_n^{a_n-1}$ in $f$.  Then
%\begin{equation}
%\label{COEFF}
% c_d = \sum_{x = (x_1,\ldots,x_n) \in X} \frac{f(x)}{\prod_{i=1}^n 
%\varphi_i'(x_i)}.
%%\prod_{y_i \in X_i \setminus \{x_i\}} (x_i-y_i)}. 
%\end{equation}
%\end{thm}
%\begin{proof}
%By Lemma \ref{TOPPEDLEMMA}, $c_d(f) = c_d(r_f)$.  Apply the Atomic Decomposition %(\ref{ATOMICDECOMPOSITION}).
%\end{proof}


%\begin{thm}(Schauz Nonuniqueness Theorem \cite[Cor. 3.4]{Schauz08a})
%\label{NONUNIQUENESSTHM}
%\label{FORROWSCHMITTCOR}
%\label{KEYSCHAUZCOR}
%Let $R$ be a ring, let $f \in R[t_1,\ldots,t_n]$, and let $A_1,\ldots,A_n$ be nonempty %finite subsets of $R$.  Put $a_i = \# A_i$, $d = (a_1-1,\ldots,a_n-1)$ and $A = %\prod_{i=1}^n A_i$.  We suppose: \\
%(i) $A$ satisfies Condition (D).  \\
%(ii) We have $\deg f < \sum_{i=1}^n (a_i-1)$.  \\
%Then $\# \{a \in A \mid f(a) \neq 0 \} \neq 1$.
%\end{thm}
%\begin{proof}
%Applying Theorem \ref{GENCOEFFTHM}b), we get
%\[ 0 = \sum_{x \in X} \frac{f(x)}{ \prod_{i=1}^n \varphi_i'(x_i)}. \]
%It is not possible for a sum to be zero if precisely one term is nonzero!
%\end{proof}





\subsection{The Restricted Variable Chevalley-Warning Theorem}
%\textbf{} \\ \\ \noindent
For a ring $R$ and $x = (x_1,\ldots,x_n) \in R^n$, we put $w(x) = \# \{1 \leq i \leq n \mid x_i \neq 0 \}$.

\begin{thm}(Restricted Variable Chevalley-Warning Theorem)  \label{RESVARCHEV}
Let $P_1,\ldots,P_r \in \F_q[t] = \F_q[t_1,\ldots,t_n]$ be polynomials of 
degrees $d_1,\ldots,d_r$.  For $1 \leq i \leq n$, let $\varnothing \neq X_i 
\subseteq \F_q$ be subsets, put $X = \prod_{i=1}^n X_i$ and also 
\[V_X = \{ x = (x_1,\ldots,x_n) \in X \mid 
P_1(x) = \ldots = P_r(x) = 0 \}. \]
% \ \zz_X = \# V_X. \]
Suppose that $(d_1+\ldots+d_r)(q-1) < \sum_{i=1}^n \left( \# X_i - 1 \right)$.  Then: \\
a) As elements of $\F_q$, we have
\begin{equation}
\label{RVCWEQ1}
 \sum_{x \in V_X} \frac{1}{\prod_{i=1}^n \varphi_i'(x_i)} = 0 
\end{equation}
and thus \cite{Schauz08a} \cite{Brink11} 
\begin{equation}
\label{RVCWEQ2}
 \# V_X \neq 1. 
\end{equation}
b) (Chevalley-Warning \cite{Chevalley35}, \cite{Warning35}) If $\sum_{i=1}^r d_i < 
n$, then $p \mid \# V_{\F_q^n}$. \\
% \{ x \in \F_q^n \mid \forall i, \ P_i(x) =  0 \}$.  \\
c) (Wilson \cite{Wilson06}) If $(d_1 + \ldots + d_r)(q-1) < n$, then 
\[ \# \{ x \in V_{ \{0,1\}^n} \mid  w(x) \equiv 0 \pmod{2}\} \equiv \# \{ x \in V_{\{0,1\}^n} \mid w(x) \equiv 1 \pmod{2}\} \pmod{p}. \]
d) If $(d_1+\ldots+d_r)(q-1) < (q-2)n$, then 
\[ \sum_{x \in V_{\F_q^n}} x_1 \cdots x_n = 0. \]
%e) Suppose $\car F \neq 2$, and let $X_1 = \ldots = X_n = \{-1,0,1\}$.  If %$\deg f \leq 2n$, then 
%\[ c_{\dd} = (-1)^n \sum_{x \in \{-1,0,1\}^n} \frac{f(x)}{(-2)^{w(x)}}. \]
%WARNING: the above requires some correction.
\end{thm}
\begin{proof}
a) We define
\[
P(t) = \chi_{P_1,\ldots,P_r}(t) =  \prod_{i=1}^r \left(1-P_i(t)^{q-1}\right),
\]
so \[\deg P = (q-1)(d_1+\ldots+d_r) < \sum_{i=1}^n \left( \# X_i - 1 \right) \] 
and thus the coefficient of $t_1^{\# X_1-1} \cdots 
t_n^{\# X_n-1}$ in $P$ is $0$.  Applying the Coefficient Formula (Theorem \ref{COEFFTHM}), we get
\[ 0 = \sum_{x \in X}  \frac{P(x)}{\prod_{i=1}^n \varphi_i'(x_i)} = 
 \sum_{x \in V_X} \frac{1}{\prod_{i=1}^n \varphi_i'(x_i)} \in \F_q. \]
Parts b) through d) follow from part a) by taking $X$ to be, respectively, 
$\F_q^n$, $\{0,1\}^n$ and $(\F_q^{\times})^n$, and computing the $\varphi_i'(t_i)'s$.  The details are left to the reader.
%b) In part a) take $X = \F_q^n$.  \\
%c) In part a) take $X = \{0,1\}^n$.  \\
%d) In part a) take $X = (\F_q^{\times})^n$.  
\end{proof}




\section{Further Analysis of the Evaluation Map}

\subsection{The Finitesatz holds only over a field}
%\textbf{} \\ \\ \noindent
If a ring $R$ is not a field and $X \neq \varnothing$, the assertion of Theorem \ref{FRN}a) remains meaningful with $R$ in place of $F$, but it is false.  
Let $x \in X$. Since $R[\underline{t}]/\mm_x \cong R$ is not a field, $\mm_x$ 
is not maximal.  Let $J$ be an ideal with $\mm_x \subsetneq J \subsetneq R[\underline{t}]$, and let $f \in J \setminus \mm_x$.  Then $V_X(J) \subset V_X(\mm_x) = \{x\}$, 
and since $f \notin \mm_x$, $f(x) \neq 0$.  Thus
\[I(V_X(J)) = I(\varnothing) = R[\underline{t}] \supsetneq J = J + I(X). \]

\subsection{Towards an Infinitesatz}
%\textbf{} \\ \\ \noindent
We revisit the formalism of $\S$ 2.2: let $R$ be a ring and let $X \subset R^n$.
\\ \\
For a subset $A \subset R^n$ we define the \textbf{Zariski closure} $\overline{A} = V(I(A))$.  Thus $\overline{A}$ is the set of points 
at which any polynomial which vanishes at every point of $A$ must also vanish.  A subset $A$ is \textbf{algebraic} if $A = \overline{A}$ and \textbf{Zariski-dense} 
if $\overline{A} = R^n$.  When $R$ is a domain 
the algebraic subsets are the closed sets of a topology, the \textbf{Zariski topology}.
%\footnote{When $R$ is an algebraically closed field, this is done in a first course %in %algebraic geometry.  The arguments go through whenever $R$ is a domain.  %Alternately, %when $R$ is a domain, the natural map $(x_1,\ldots,x_n) \in R^n \mapsto 5\langle %t_1-x_1,\ldots,t_n-x_n \rangle$ gives an embedding $R^n \hookrightarrow %\Spec R[\underline{t}]$, %and the Zariski topology on $R^n$ is the one that $R^n$ inherits as a %subspace of %$\Spec R[t]$ endowed with the Zariski topology in the sense of %\cite[$\S$ IX.5]{Lang}.}  Since $\{(x_1,\ldots,x_n)\} = V( \langle t_1 - %x_1,\ldots,t_n-x_n \rangle)$, it follows that all finite sets are algebraic. 
Over an arbitrary ring 
this need not hold and some strange things can happen: for instance if $R = \Z/6\Z$ and $n = 1$ then $\overline{ \{2,3\} } 
= \{0,2,3,5\}$.  In fact for any composite positive 
integer $m \neq 4$, there is a subset $A \subset \Z/m\Z$ which is not algebraic \cite{Sierpinski54}, \cite{Choj56}.  Some partial results towards an explicit description of the operator $A \mapsto \overline{A}$ for subsets of $\Z/m\Z$
have recently been obtained by B. Bonsignore.
\\ \\
If $F$ is an algebraically closed field and $X \subset F^n$ is algebraic, then using Hilbert's Nullstellensatz, for all ideals $J$ of $F[\underline{t}]$, 
\[ I(V_X(J)) = I(V(J) \cap X) = I(V(J) \cap V(I(X))) \] \[ =I(V(J \cup I(X))) = I(V(J+I(X))) = \rad (J + I(X)). \]
When $X$ is infinite, we {\sc claim} the ``$\rad$'' cannot be removed in general.  
\\
\noindent
{\sc proof of claim}: Suppose $\rad (J + I(X)) = J + I(X)$ for all $J$.  Equivalently, every ideal 
$J \supset I(X)$ is a radical ideal.  Then for any element $x$ in the quotient ring $F[\underline{t}]/I(X)$, since $(x^2)$ is radical we must have $(x) = (x^2) = (x)^2$.  It follows  (e.g. \cite[p. 35, p. 44, p. 90]{Atiyah-Macdonald}) that $F[\underline{t}]/I(X)$ is Noetherian and absolutely flat, hence is Artinian, hence has only finitely many maximal ideals.  Since $x \mapsto \mm_x$ is an injection from $X$ to the set of maximal ideals of $F[\underline{t}]/I(X)$, $X$ is finite.  
\\ \\
The case of an arbitrary subset over an arbitrary ring $R$ is much more challenging.  In fact, even determining whether the evaluation map $E_X: R[\underline{t}] \ra R^X$ is surjective -- \textbf{existence of interpolation polynomials} -- or injective -- \textbf{uniqueness of interpolation polynomials} --
becomes nontrivial.  In the next section we address these questions, but we are not able to resolve them completely.  

\subsection{Injectivity and Surjectivity of the Evaluation Map}
%\textbf{} \\ \\ \noindent

\begin{lemma}
\label{LAMLEMMA}
Let $R$ be a ring.  Let $M_1$ and $M_2$ be free $R$-modules, with bases 
$\mathcal{B}_1$ and $\mathcal{B}_2$.  If $\iota: M_1 \ra M_2$ is an injective $R$-module homomorphism, then $\# \mathcal{B}_1 \leq \# \mathcal{B}_2$.
\end{lemma}
\begin{proof}
Combine \cite[Cor. 1.38]{LMR} and \cite[Ex. 1.24]{EMR}.
\end{proof}

\begin{lemma}
\label{LINEARALGEBRAFACT}
Let $R$ be a ring, and let $X$ be an infinite set.  Then $R^X$ is \emph{not} a countably generated $R$-module.
\end{lemma}
\begin{proof}
Step 1: For $x \in \R$, let $A_x = \{ y \in \Q \mid y < x\}$, and let $\mathcal{C}_{\Q} = \{ A_x\}_{x \in \R}$.  Then $\mathcal{C}_{\Q} \subset 2^{\Q}$ is an uncountable linearly ordered family of nonempty subsets of $\Q$.  Since $X$ is infinite, 
there is an injection $\iota: \Q \hookrightarrow X$; then $\mathcal{C} = \{ \iota(A_x)\}_{x \in \R}$ is an uncountable linearly ordered family of nonempty subsets of $X$.  
\\ 
Step 2: For each $A \in \mathcal{C}$, let $1_A$ be the characteristic function of $A$.  Then $\{1_A\}_{A \in \mathcal{C}}$ is an $R$-linearly independent set: let $A_1,\ldots,A_n \in \mathcal{C}$ and $\alpha_1,\ldots,\alpha_n \in R$ be such that $\alpha_1 1_{A_1} + \ldots + \alpha_n 1_{A_n} \equiv 0$.  We may order the $A_i$'s such that $A_1 \subset \ldots \subset A_n$ and thus there is $x \in A_n \setminus \bigcup_{i=1}^{n-1} A_{i}$.  Evaluating at $x$ gives $\alpha_n = 0$.  In a similar manner we find that $\alpha_{n-1} = \ldots = \alpha_1 = 0$.
\\ 
Step 3: Suppose $R^X$ is countably generated: thus there is a surjective $R$-module homomorphism $\Phi: \bigoplus_{i=1}^{\infty} R \rightarrow R^X$.  For each $A \in \mathcal{C}$, choose $e_A \in \Phi^{-1}(1_A)$ and put $\mathcal{S} = \{ e_A \mid A \in \mathcal{C} \}$.  By Step 2, $\mathcal{S}$ is uncountable and $R$-linearly independent, so it spans a free $R$-module with an uncountable basis which is 
an $R$-submodule of $\bigoplus_{i=1}^{\infty} R$, contradicting Lemma \ref{LAMLEMMA}.
\end{proof}

\begin{thm}
\label{EVALSURJ}
If $X \subset R^n$ is infinite, then $E_X: R[\underline{t}] \ra R^X$ is \emph{not} surjective.
\end{thm}
\begin{proof}
If $E_X: R[\underline{t}] \ra R^X$ were surjective, then $R^X$ would be a countably generated $R$-module, contradicting Lemma \ref{LINEARALGEBRAFACT}.
% We will give one argument which works when $F$ is Noetherian and another %argument that works in the general case. 
%\\ \indent
%Suppose first that $F$ is Noetherian.  Then by 
%the Hilbert Basis Theorem $F[\underline{t}]$ is Noetherian, so if $E_X$ were surjective, 
%then $F^X$ would be a homomorphic image of a Noetherian ring and thus %Noetherian.  
%But when $X$ is infinite $F^X$ is certainly not Noetherian, as can be seen in %many different ways.  For instance, let $I \subset F^X$ be the set of all %functions which vanish at all but finitely many points of $X$.  Then $I$ is an %ideal of $F^X$ which is not finitely generated.  
%\\ \indent
%Now let $F$ be any domain, with fraction field $K$.  Since $X$ is %infinite, $F^X$ %is not a countably 
%generated $F$-module and $E_X$ cannot be surjective.  When $F$ is countable, %this %follows from cardinality considerations.  In general it is an annoyingly %nontrivial linear algebra fact. \\
%(ii) $\implies$ (i): For $1 \leq i \leq n$, let $\pi_i: F^n \ra F$ by %$(x_1,\ldots,x_n) \mapsto x_i$, and let $X_i = \pi_i(X)$.  Since for $X \subset Y %\subset F^n$ the canonical restriction map $F^Y \ra F^X$ is surjective, we may %prove the result after replacing $X$ by the larger finite subset $\tilde{X} = %\prod_{i=1}^n X_i$.  For $\alpha = (\alpha_1,\ldots,\alpha_n) \in \tilde{X}$, let
%\begin{equation}
%\label{DELTAFUNCTION}
% \delta_{\alpha}(t)= \frac{\prod_{i=1}^n \prod_{x_i \in X_i \setminus \{\alpha_i\}} %(t_i-x_i)}{ \prod_{i=1}^n \prod_{x_i \in X_i \setminus \{\alpha_i\}} %(\alpha_i-x_i)}. \end{equation}
%Then, as a function on $\tilde{X}$, $\delta_{\alpha}$ is the characteristic 
%function of $\{ \alpha \}$: $\delta_{\alpha}(\alpha) = 1$ and $\delta_{\alpha}(x) = %0$ for all $x \in \tilde{X} \setminus \{\alpha\}$.  Then $\{ \delta_{\alpha} %\}_{\alpha \in \tilde{X}}$ is a basis for $F^{\tilde{X}}$, so every element of %$F^{\tilde{X}}$ arises by evaluating a polynomial.  
\end{proof}
\noindent
If $Y \subset X \subset R^n$, restricting functions from $X$ 
to $Y$ is a surjective $R$-algebra homomorphism $\mathfrak{r}_Y: R^X \ra R^Y$.  
We have $E_Y = \mathfrak{r}_Y \circ E_X$, so if $E_X$ is surjective, so is 
$E_Y$.
\\ \\
Let $\pi_i: R^n \ra R$ be the $i$th projection map: $\pi_i: (x_1,\ldots,x_n) \mapsto x_i$.  For a subset $X \subset R^n$, we define the \textbf{cylindrical hull} $\mathcal{C}(X)$ as $\prod_{i=1}^n \pi_i(X)$: it is the unique minimal cylindrical subset containing $X$, and it is finite iff $X$ is.  

\begin{prop}
\label{PARTIALSURJ}
Let $X \subset R^n$ be finite.  \\
a) If $\mathcal{C}(X)$ satisfies Condition (F), then $E_X$ is surjective.  \\
b) If there is a nonempty cylindrical subset $Y = \prod_{i=1}^n Y_i \subset X$ which does not satisfy Condition (F), then $E_X$ is not surjective.
\end{prop}
\begin{proof}
a) Since $X \subset \mathcal{C}(X)$, it suffices to show that $E_{\mathcal{C}(X)}$ 
is surjective, and we have essentially already done this: under Condition (F) we may \emph{define} $r_X(f) = \sum_{x \in X} f(x) \delta_{X,x}(t)$, and as in $\S$ 3.3 we see that $E(r_X(f)) = f$.  \\
b) There is $1 \leq i \leq n$ and $y_i \neq y_i' \in Y_i$ such that 
$y_1-y_2 \notin R^{\times}$, hence a maximal ideal $\mm$ of 
$R$ with $y_1-y_2 \in \mm$.  For all $j \neq i$, choose $y_j \in Y_j$; let 
$y = (y_1,\ldots,y_n)$; and let $y'$ be obtained from $y$ by changing the 
$i$th coordinate to $y_i'$.  For any $f \in F[\underline{t}]$, $f(y) \equiv f(y') \pmod{\mm}$, 
so $f(y) - f(y') \in \mm$.  Hence the function $\delta_{Y,y}: Y \ra R$ which maps $y$ to $1$ and every other element of $Y$ to $0$ does not lie in the image of the evaluation map.  Thus $E_Y$ is not surjective, so $E_X$ cannot be surjective. 
\end{proof}
\noindent
Thus if $X$ is itself cylindrical, the evaluation map is surjective iff $X$ satisfies Condition (F): this result is due to Schauz.  Proposition \ref{PARTIALSURJ} is the mileage one gets from this in the general case.  When every cylindrical subset of $X$ 
satisfies condition (F) but $\mathcal{C}(X)$ does not, the question of the existence of interpolation polynomials is left open, to the best of my knowledge even e.g. over $\Z$.    
\\ \\
We say that a ring $R$ is \textbf{(F)-rich} (resp. \textbf{(D)-rich}) if for every $d \in \Z^+$ there is a $d$-element subset of $R$ satisfying Condition (F) (resp. Condition (D)).  If $\iota: R \hookrightarrow S$ is a ring embedding and $R$ is 
(F)-rich, then $S$ is (F)-rich, hence also (D)-rich.  
%A local ring if (F)-rich 
%iff its residue field is infinite.  


\begin{prop}
\label{PROP14}
Let $R$ be a ring and $X \subset R^n$.  Consider the following assertions: \\
(i) $E_X$ is injective.  \\
(ii) $X$ is infinite and Zariski-dense.  \\
a) We always have (i) $\implies$ (ii).  \\
b) If $R$ is (D)-rich -- e.g. if it contains an (F)-rich subring -- then (ii) $\implies$ (i). \\
c) If $R$ is finite, a domain, or an algebra over an infinite field, then (ii) $\implies$ (i). \\
d) If $R$ is an infinite Boolean ring -- e.g. $R = \prod_{i=1}^{\infty} \Z/2\Z$ -- and $X = R^n$, then (ii) holds and (i) does not.
\end{prop}
\begin{proof}
a) By contraposition: suppose first that $X$ is finite.  Then 
$F^X$ is a free $F$-module of finite rank $\# X$ and $F[\underline{t}]$ is a free $F$-module of infinite rank, so $E$ cannot be injective.  Now suppose $X$ is not 
Zariski-dense: then there is 
$y \in F^n \setminus X$ and $f \in F[\underline{t}]$ such that $E(f)|_X \equiv 0$ 
and $E_X(f)(y) \neq 0$, hence $0 \neq f \in \Ker E$.  \\
b) Let $f \in \Ker E_X = I(X)$, and let $d = \deg f$.  Since $X$ is Zariski-dense in $F^n$, $f(x) = 0$ for all $x \in F^n$.  Since $R$ is (D)-rich, there is a $S \subset R$ of cardinality $d+1$ satisfying Condition (D).  Put $X = \prod_{i=1}^n S$.  
Then $f \in \mathcal{R}_X$ and $f(x) = 0$ for all $x \in X$, so $f = 0$ by Theorem \ref{CATS}.  c) This is immediate from part b). \\
%c) If $R$ is finite then (ii) $\implies$ (i) is vacuous, while if $R$ is infinite 
%it is (D)-rich. \\
d) Since $R$ is infinite, $R^n$ is infinite and Zariski-dense.  Since $R$ is Boolean, the polynomial $t_1^2-t_1$ evaluates to zero on every $x \in R^n$.  
\end{proof}

\subsection*{Acknowledgments}
My interest in Combinatorial Nullstellens\"atze and connections to Chevalley's Theorem was kindled by correspondence with John R. Schmitt.  The main idea for the proof of Lemma \ref{LINEARALGEBRAFACT} is due to Carlo Pagano.  I thank Emil Je\v r\'abek for introducing me to the Finite 
Field Nullstellensatz.  I am grateful to the referee for a careful and insightful reading.
 

\begin{thebibliography}{KMR11}

%\bibitem[AD93]{Alon-Dubiner93} N. Alon and M. Dubiner, \emph{Zero-sum sets of %prescribed size}. Combinatorics, Paul Erd\H os is eighty, Vol. 1, 33–50,
%Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993. 

%\bibitem[AF93]{Alon-Furedi93} N. Alon and Z. F\"uredi, \emph{Covering the cube by %affine hyperplanes}. Eur. J. Comb. 14 (1993), 79-83.

\bibitem[Al99]{Alon99} N. Alon, \emph{Combinatorial Nullstellensatz}. Recent trends in combinatorics (M\'atrah\'aza, 1995). Combin. Prob. Comput. 8 (1999), 7--29.

%\bibitem[Al99]{Alon99} N. Alon, \emph{Combinatorial Nullstellensatz}. 
%Recent trends in combinatorics (M\'atrah\'aza, 1995). Combin. Probab. Comput. 8 (1999), 7–29. 



% 



\bibitem[AM]{Atiyah-Macdonald} M.F. Atiyah and I.G. Macdonald, \emph{Introduction to commutative algebra}.  Addison-Wesley Publishing 
Co., Reading Mass.-London-Don Mills, Ont. 1969.

\bibitem[AT92]{Alon-Tarsi92} N. Alon and M. Tarsi \emph{Colorings and orientations of graphs}. Combinatorica 12 (1992), 125--134.

%\bibitem[Ax64]{Ax64} J. Ax, \emph{Zeroes of polynomials over finite fields}.
%Amer. J. Math. 86 (1964), 255--261.

\bibitem[Br87]{Brownawell87} W.D. Brownawell, \emph{Bounds for the degrees in the Nullstellensatz.} Ann. of Math. (2) 126 (1987), 577--591.

%Brownawell, W. Dale(1-PAS)
%Bounds for the degrees in the Nullstellensatz.
%Ann. of Math. (2) 126 (1987), no. 3, 577-–591

\bibitem[Br11]{Brink11} D. Brink, \emph{Chevalley's theorem with restricted variables}. 
Combinatorica 31 (2011), 127--130.

\bibitem[CFS14]{CFS14} P.L. Clark, A. Forrow and J.R. Schmitt, \emph{Warning's Second Theorem with Restricted Variables}. {\tt http://arxiv.org/abs/1404.7793}

\bibitem[Ch35]{Chevalley35} C. Chevalley, \emph{D\'emonstration d'une hypoth\'ese de M. Artin.}
Abh. Math. Sem. Univ. Hamburg 11 (1935), 73--75.

\bibitem[Ch56]{Choj56} M.M. Chojnacka-Pniewska, \emph{Sur les congruences aux racines donn\'ees}. 
Ann. Polon. Math 3 (1956), 9--12.

%\bibitem[EH79]{EH79} D. Eisenbud and M. Hochster, \emph{A Nullstellensatz with %nilpotents and Zariski's main lemma on holomorphic functions}.
%J. Algebra 58 (1979), 157-–161.

\bibitem[EMR]{EMR} T. Y. Lam, \emph{Exercises in modules and rings}.
Problem Books in Mathematics. Springer, New York, 2007.

%\bibitem[Ga09]{Gao09} S. Gao, \emph{Counting Zeros over Finite Fields Using %Gr\"obner Bases}.  2009 master's thesis, Carnegie Mellon University.

%\bibitem[Ge91]{Germundsson91} R. Germundsson, \emph{Basic Results on Ideals and %Varieties in Finite Fields}. Technical report, Department of Electrical %Engineering, L\"inkoping University, 1991. 

%\bibitem[KMR11]{KMR11} G. K\'os, T. M\'esz\'aros and L. R\'onyai, \emph{Some %extensions of Alon's Nullstellensatz}. Publ. Math. Debrecen 79 (2011), no. 3-4, %507–-519.

\bibitem[Ko88]{Kollar88} J. Koll\'ar, \emph{Sharp effective Nullstellensatz}. J. Amer. Math. Soc. 1 (1988), 963--875.

\bibitem[KMR12]{KMR12} G. K\'os, T. M\'esz\'aros and L. R\'onyai, \emph{Some extensions of Alon's Nullstellensatz}. Publ. Math. Debrecen 79 (2011), 507-519. 

\bibitem[KP12]{Karasev-Petrov12} R.N. Karasev and F.V. Petrov, \emph{Partitions of nonzero elements of a finite field into pairs}. Israel J. Math. 192 (2012), 143-156. 

%\bibitem[KR12]{KR12} G. K\'os and L. R\'onyai, \emph{Alon's Nullstellensatz for %multisets}. Combinatorica 32 (2012) 589–605.

\bibitem[L]{Lang} S. Lang, \emph{Algebra}. Revised third edition. Graduate Texts in Mathematics, 211. Springer-Verlag, New York, 2002. 

\bibitem[La10]{Lason10} M. Laso\'n, \emph{A generalization of combinatorial Nullstellensatz}. Electron. J. Combin. 17 (2010), Note 32, 6 pp. 

\bibitem[LMR]{LMR} T. Y. Lam, \emph{Lectures on modules and rings}. 
Graduate Texts in Mathematics, 189. Springer-Verlag, New York, 1999.

\bibitem[Sc08]{Schauz08a} U. Schauz, \emph{Algebraically solvable problems: describing polynomials as equivalent to explicit solutions}. 
Electron. J. Combin. 15 (2008), no. 1, Research Paper 10, 35 pp. 

%\bibitem[Sc08b]{Schauz08} U. Schauz, \emph{On the dispersions of the polynomial %maps over finite fields}. Electron. J. Combin. 15 (2008), no. 1, Research Paper %145, 16 pp. 

\bibitem[Si54]{Sierpinski54} W. Sierpi\'nski, \emph{Remarques sur les racines d'une congruence}. Ann. Polon. Math. 1 (1954), 89-90.

\bibitem[Ta14]{Tao14} T. Tao, \emph{Algebraic combinatorial geometry: the polynomial method in 
arithmetic combinatorics, incidence combinatorics, and number theory}. EMS Surv. Math. Sci. 1 (2014), 1--46.

\bibitem[Te66]{Terjanian66} G. Terjanian, \emph{Sur les corps finis}. C. R. Acad. Sci. Paris S\'er. A-B 262 (1966), A167--A169.

\bibitem[Wa35]{Warning35} E. Warning, \emph{Bemerkung zur vorstehenden Arbeit von Herrn Chevalley}. 
Abh. Math. Sem. Hamburg 11 (1935), 76--83.

\bibitem[Wi06]{Wilson06} R.M. Wilson, \emph{Some applications of polynomials in combinatorics}. IPM Lectures, May, 2006.

%\bibitem[Ze13]{Zeilberger13} D. Zeilberger, 
%{\tt http://www.math.rutgers.edu/$\sim$zeilberg/mamarim/mamarimhtml/qdyson.html}

\end{thebibliography}

\end{document}


Lason', M. (PL-JAGLMC-TC)
A generalization of combinatorial Nullstellensatz. (English summary)
Electron. J. Combin. 17 (2010), no. 1, Note 32, 6 pp. 


MR1249703 (94j:11016)
Alon, N.(IL-TLAV); Dubiner, M.(IL-TLAV)
Zero-sum sets of prescribed size. (English summary) Combinatorics, Paul Erd�s is eighty, Vol. 1, 33--50,
Bolyai Soc. Math. Stud., J�nos Bolyai Math. Soc., Budapest, 1993. 

However, it is by no means as easy to prove Theorem \ref{EGZTHM} as the ``amusing'' Theorem \ref{EASYZSUMTHM}: we urge the 
reader to try to find a proof for herself.  Indeed, the ``EGZ Theorem'' is a celebrated and influential result in 
combinatorial number theory, and by now there are many different proofs.  In a 1989 article, C. Bailey and R.B. Richter 
gave a very elegant proof as an application of the Chevalley-Warning theorem.  We follow their proof here.


The basic idea is as follows: we 
can define two polynomials $P(t)$ and $Q(t)$ with the following properties: for $x \in \F_q^n$, $P(x)$ is equal to $1$ if 
$P_1(x) = \ldots = P_r(x) = 0$ and is otherwise $0$; $Q(x) = 1$ if $x = 0$ and is $1$ for all other $x \in \F_q^n$; 
$Q = \tilde{Q}$ has degree less than $q$ in each variable; $\deg(P) < \deg(Q)$.  If then there were no nontrivial solutions 
to the polynomial system $P_1(x) = \ldots = P_r(x) = 0$ then we would have $\Phi(P) = \Phi(Q)$
\\ \\




\subsection{Gateway to the Polynomial Method}

\begin{lemma}(Alon-Tarsi \cite[Lemma 2.1]{Alon-Tarsi92})
\label{11.6.2}
Let $k$ be a field, $n \in \Z^+$, and $f(t) \in k[t] = k[t_1,\ldots,t_n]$; for $1 \leq i \leq n$, let $d_i$ be the $t_i$-degree of $f$, let $S_i$ be a subset of $k$ with $\# S_i > d_i$, and let $S = \prod_{i=1}^n S_i$.  If $f(x) = 0$ for all $x \in S$, then $f = 0$.   
\end{lemma}
\begin{proof}
We go by induction on $n$.  The case $n = 1$ is truly basic: a nonzero univariate polynomial over a field has no more roots than its degree.  Now suppose $n \geq 2$ and that the result holds for polynomials in $n-1$ variables.  We will use the ``identity'' $k[t_1,\ldots,t_{n-1},t_n] = 
k[t_1,\ldots,t_{n-1}][t_n]$: thus we write 
\[ f= \sum_{i=0}^{d_n} f_i(t_1,\ldots,t_{n-1}) t_n^i\]
with $f_i \in k[t_1,\ldots,t_{n-1}]$.  For $(x_1,\ldots,x_{n-1}) \in F^{n-1}$, the polynomial $f(x_1,\ldots,x_{n-1},t_n) \in k[t_n]$ has degree at most $d_n$ and vanishes for all $\# S_n > d_n$ elements $x_n \in S_n$, so it is identically zero, i.e., $f_i(x_1,\ldots,x_{n-1}) = 0$ for all $0 \leq i \leq t_n$.  By induction, each $f_i(t_1,\ldots,t_{n-1})$ is the zero polynomial and thus $f$ is the zero polynomial.  
\end{proof}
\noindent
If in Lemma \ref{11.6.2} we take $F = \F_q$ and $S_i = \F_q$ for all $1 \leq i \leq n$, then we get precisely the assertion that a reduced polynomial which induces the 
zero function is the zero polynomial.  Thus if $f$ and $g$ are reduced polynomials which induce the same function, then $f-g$ is a reduced polynomial which induces the zero function, so $f-g = 0$ and $f =g$.  Moreover, although no mention of Chevalley is made in \cite{Alon-Tarsi92}, the method of proof of Lemma \ref{11.6.2} is identical to Chevalley's: c.f. \cite[Lemme 1]{Chevalley35}.
\\ \\
The Alon-Tarsi Lemma however makes the proof of Theorem \ref{WARTHM}a) a bit easier.  As before, suppose $V = \{x\}$, and consider 
\[ P(t) = \chi_{P_1,\ldots,P_r}(t) =  \prod_{i=1}^r \left(1-P_i(t)^{q-1}\right) \]
and 
\[Q_Z(t) = \delta_x(t) =  \prod_{i=1}^n 1-(t_i-x_i)^{q-1}. \]
But now consider also 
\[ R(t) = Q_Z(t) - P(t). \]
By construction, $R(x) = 0$ for all $x \in \F_q^n$.  Since $\deg P = (q-1)(d_1 + \ldots + d_r) < \deg Q_Z(t) = (q-1)n$, the coefficient 
of $t_1^{q_1} \cdots t_n^{q_n}$ in $R(t)$ is the same as that of $Q_Z(t)$, namely 
$(-1)^n$.  



\footnote{It would be irresponsible not to mention that in the
early 20th century quadratic reciprocity found an incredibly more
general formulation in the ``class field theory'' of (most
notably) Emil Artin; this subject is one of the true cornerstones
of modern number theory. However, it is one topic for which many
(myself included) find it daunting to explain ``what is really
going on''.  In particular, in class field theory one meets the
``Artin reciprocity map'' and a certain fundamental result
concerning this map is called the ``reciprocity law'' and referred
to in passing as the appropriate analogue of quadratic reciprocity
in this general context. If you ever take such a class, I invite
you to ask the instructor exactly how Artin reciprocity
generalizes quadratic reciprocity: either s/he will squirm, you
will, or both.}





\subsection{Proof of Chevalley's Theorem} 
%\textbf{} \\ \\ \noindent
As in the statement of the theorem, suppose we have $d_1,\ldots,d_r \in \Z^+$ 
such that $d_1 + \ldots + d_r < n$ and polynomials $P_1,\ldots,P_r \in \F_q[t] = \F_q[t_1,\ldots,t_n]$ with 
$P_i(0) = 0$ for all $i$ and $\deg(P_i) = d_i$.  Now define polynomials $P(t),Q(t),R(t) \in \F_q[t]$ as follows:
\begin{equation}
\label{PtEQ}
P(t) =  \prod_{i=1}^r \left(1-P_i(t)^{q-1}\right), 
\end{equation}
\begin{equation} Q(t) = \prod_{j=1}^n \left(1-t_i^{q-1}\right), \end{equation}
\begin{equation} R(t) = \tilde{P}(t)-Q(t), \end{equation}
where $\tilde{P}$ is the unique polynomial which is congruent to $P$ modulo $\Ker(\Phi)$ and has degree less than $q$ in 
each of its variables.  Why?  Observe that for any $1 \leq i \leq r$ and 
$(x_1,\ldots,x_n) \in \F_q^n$ the expression $(1-P_i(x_1,\ldots,x_n)^{q-1})$
is equal to $0$ if $P_i(x_1,\ldots,x_n) \neq 0$ and is equal to $1$ is $P_i(x_1,\ldots,x_n) = 0$.  From this it follows 
that $P(t) = \prod_{i=1}^r \left(1-P_i(t)^{q-1}\right)$, when evaluated at a point $x = (x_1,\ldots,x_n) \in \F_q^n$, is equal to $1$ if $P_1(x) = \ldots = P_r(x) = 0$ and 
is equal to $0$ otherwise.  By similar, but simpler, reasoning, $Q(x) = 0$ iff $x = 0$.  Therefore, assuming for a 
contradiction that the $P_i$'s do not have any nontrivial common solution $x$, we have $\tilde{P}(x) = P(x) = Q(x)$ for all 
$x \in \F_q^n$.  Therefore $R(t)$ lies in the kernel of the evaluation map.  However, its degree in each $t_i$ is less than $q$, so $R(t)$ is the zero 
polynomial.  Thus $\tilde{P} = Q$ and in particular \[\deg(\tilde{P}) = \deg(Q) = (q-1)n. \] But on the other hand, since passing 
from $P$ to $\tilde{P}$ involves a sequence of operations none of which raise the degree, we must have 
\[\deg(\tilde{P}) \leq \deg(P) = \sum_{i=1}^r (q-1) \deg(P_i) = (q-1)\sum_{i=1}^r d_i < (q-1)n. \]
This gives a contradiction, so our assumption that there was no nontrivial simultaneous solution to $P_1(t) = \ldots = 
P_r(t) = 0$ must have been false.


\subsection{First Proof of Warning's Theorem} \textbf{} \\ \\
Looking back at the proof of Chevalley's theorem, notice that a prominent role was played by the polynomial 
\[Q(t) = \prod_{i=1}^n (1-t_i^{q-1}). \]
An examination of exactly why this was the case will lead us to a proof of Warning's theorem.  
\\ \\
The significance of $Q(t)$ is that it is the unique reduced polynomial which represents the function 
\[{\bf 1}_0: \F_q^n \ra \F_q \]
which takes $0 = (0,\ldots,0)$ to $1$ and every other element to $0$.  In other words, ${\bf 1}_0$ is the characteristic 
function of the origin in $\F_q^n$.  More generally, for any subset $S \subset \F_q^n$ we can consider the characteristic 
function ${\bf 1}_S$ which takes $x \in S$ to $0$ and $x \in (\F_q^n \setminus S)$ to $1$.  This needs to be taken with the 
following grain of salt: we are calling an $\F_q$-valued function a characteristic function, whereas normally a characteristic 
function has values in $\R$ or at least in some domain of characteristic $0$.  Thus ${\bf 1}_S$ is more precisely the 
reduction modulo $p$ of the usual characteristic function ${\bf 1}_S$; any function $f: \F_q^n \ra \Z$ such that 
$f(x) \equiv {\bf 1}_S \pmod p$ for all $x \in \F_q^n$ would serve as well.
\\ \\
What makes the proof of Chevalley's theorem work is that the reduced polynomial function ${\bf 1}_0$ has ``maximal 
complexity'': its reduced degree in each variable $t_i$ is $q-1$, the largest possible reduced degree.  Also its total 
degree is $n(q-1)$, so if $P(t)$ is any polynomial of smaller total degree, then by Exercise X.X, the reduced 
total degree of $P(t)$ is less than the (reduced) total degree of $Q(t)$ so $P(t)$ and $Q(t)$ determine different polynomial 
functions.
\\ \\
To extend the proof, let us compute (in some sense) the reduced polynomial corresponding to the characteristic function 
${\bf 1}_S$ of an arbitrary subset $S \subset \F_q^n$.  A basic and easy property of conventional (i.e., $\Z$-valued) 
characteristic functions is that if $S$ and $T$ are disjoint subsets of a set $\Omega$, then \[{\bf 1}_{S \cup T} = 
{\bf 1}_S + {\bf 1}_T. \]
Here $S \subset \F_n^q$ is of course finite, so 
\[{\bf 1}_S = \sum_{x \in S} {\bf 1}_x. \]
Moreover, knowing the reduced polynomial for ${\bf 1}_0$ it is easy to derive the one for ${\bf 1}_x$ by translation:
\[{\bf 1}_{(x_1,\ldots,x_n)} = \prod_{i=1}^n \left( 1-(t_i-x_i)^{q-1} \right) . \]
So take
\begin{equation}
\label{ZEQ}
Z = \{(x_1,\ldots,x_n) \in \F_q^n \ | \ P_1(x) = \ldots = P_r(x) = 0 \} 
\end{equation}
and put
\[Q_Z(t) =  \sum_{x \in Z} \prod_{i=1}^n \left( 1-(t_i-x_i)^{q-1} \right). \]
Then $Q_Z(t)$ is nothing else than the reduced polynomial representative of ${\bf 1}_Z$.  On the other hand, the 
polynomial $P(t)$ defined by (\ref{PtEQ}) above also defines the same polynomial function as ${\bf 1}_Z$.  The total degree 
of $P(t)$ is $(q-1) \sum_i d_i < (q-1)n$.  \\ \indent 
Now consider the coefficient of the monomial $t_1^{q-1} \cdots t_n^{q-1}$ in $Q_Z(t)$: it 
is $(-1)^n\# Z$.  \textbf{Assume} that $\#Z$ is not divisible by $p$.   Then this term is nonzero and $Q_Z(t)$ has degree at least $(q-1)n$.  Again, by 
Exercise X.Xb) we have 
\[ \deg(\tilde{P}) \leq \deg(P) < (q-1)n \leq \deg(Q_Z). \]
Therefore $\tilde{P} \neq Q_Z$, but both are supposed to be the reduced polynomial representative of ${\bf 1}_Z$.  This 
completes the proof!








\noindent
Chevalley's proof occurs in two steps.  The existence of a reduced polynomial equivalent to any $f \in \F_q[t]$ is an easy consequence of the observation that for every $x \in \F_q^{\times}$, $x^{q-1}  = 1$.  Because of this, whenever $f$ has a monomial in which some $t_i$ occurs to exponent $a_i$ which is at least $q$, if we simply replace $t_i^{a_i}$ by $t_i^{a_i-(q-1)}$ we do not change the associated function.  Performing this elementary reduction finitely many times we arrive at an equivalent reduced polynomial.  \\ \indent
To prove the uniqueness of the reduced representative comes down to showing that 
if a reduced polynomial $f \in \F_q[t]$ has $f(x) = 0$ for all $x \in \F_q$ then 
$f = 0$.  This is established by a fairly innocuous inductive argument, which is really a slightly more careful version of the argument that works to show that any polynomial with coefficients in an infinite field $K$ which evaluates to zero at all $x \in K^n$ is the zero polynomial.  Again, we will prove a slight refinement of this (for which Chevalley's argument adapts verbatim) later. 
\\ \\
For now I want to make a small modification of Chevalley's proof.  In fact we will prove the following stronger result, which amounts to Chevalley's Lemma plus the assertion that the evaluation map $\Phi$ is \textbf{surjective} in the finite field case.








\section{Some later work}
\noindent
Under the hypotheses of Warning's theorem we can certainly have $0$ solutions.  For instance, we could take 
$P_1(t)$ to be any polynomial with $\deg(P_1) < \frac{n}{2}$ and $P_2(t) = P_1(t) + 1$.  Or, when $q$ is odd, let 
$a \in \F_q$ be a quadratic nonresidue, let $P_1(t)$ be a polynomial of degree less than $\frac{n}{2}$ and put
$P(t) = P_1(t)^2-a$.  
\\ \\
On the other hand, it is natural to wonder: in Warning's theorem, we might actually have $\# Z \equiv 0 \mod q$?  The answer 
is now known, but it took $46$ years.  
\\ \\
Let us first consider the case of $r = 1$, i.e., a single polynomial $P$ of degree less than $n$.  In his original 
1926 paper, E. Warning proved that $\# Z$, if positive, is at least $q^{n-d}$.  And in the same 1964 paper containing the 
quick proof of Warning's theorem, J. Ax showed that $q^b \ | \ \# Z$ for all $b < \frac{n}{d}$.  By hypothesis we can 
take $b = 1$, so the aforementioned question has an affirmative answer in this case.
\\ \\
For the case of multiple polynomials $P_1,\ldots,P_r$ of degrees $d_1,\ldots,d_r$, in a celebrated 1971 paper N. Katz 
showed that $q^b \ | \ \# Z$ for all positive integers $b$ satisfying 
\[b < \frac{n-(d_1+\ldots+d_r)}{d_1} + 1. \]
Since the above fraction is by hypothesis strictly positive, we can take $b = 1$ getting indeed $\#Z \equiv 0 \pmod q$ 
in all cases.
\\ \\
These divisibilities are called estimates of \textbf{Ax-Katz type}.  It is known that there are examples in which 
the Ax-Katz divisibilities are best possible, but refining these estimates in various cases is a topic of active research: 
for instance there is a 2007 paper by W. Cao and Q. Sun, \emph{Improvements upon the Chevalley-Warning-Ax-Katz-type 
estimates}, J. Number Theory 122 (2007), no. 1, 135--141. 
\\ \\
Notice that the work since Warning has focused on the problem of getting best possible $p$-adic estimates for 
the number of solutions: that is, instead of bounds of the form $\# \Z \geq N$, we look for bounds of the form 
$\ord_p( \#Z) \geq N$.  Such estimates are closely linked to the \textbf{p-adic cohomology} of algebraic varieties, a 
beautiful (if technically difficult) field founded by Pierre Deligne in his landmark paper ''Weil II.''
\\ \\
The hypotheses of the Chevalley-Warning theorem are also immediately suggestive to algebraic geometers: (quite) roughly 
speaking there is a geometric division of algebraic varieties into three classes: Fano, Calabi-Yau, and general type.  The 
degree conditions in Warning's theorem are precisely those which give, among the class of algebraic varieties represented 
nicely by $r$ equations in $n$ variables (``smooth complete intersections''), the Fano varieties.  A recent result of 
H\'el\`ene Esnault gives the geometrically natural generalization: any Fano variety over $\F_q$ has a rational point.  There 
are similar results for other Fano-like varieties.   
\section{Sharpness of the Hypotheses in the Chevalley-Warning Theorem}


\begin{remark}
The hypothesis that $V \neq \emptyset$ is certainly needed for Theorem \ref{WARTHM}a): take for instance $r \geq 2$ and $P_2 = P_1 + 1$. \\
There are also examples with $r = 1$.  When $r = d= 1$ we have one linear 
polynomial, so of course there are zeros.  On the other hand, let $2 \leq d$.  Then there is an irreducible polynomial $f(t) \in \F_q[t]$ of degree $d$; let 
$L_1(t) = L_1(t_1,\ldots,t_n)$ be any linear polynomial and let $P_1(t) = f(L_1(t))$.  Then $V = \emptyset$.  \\
However in Diophantine applications one usually takes the polynomials $P_i$ to be 
\emph{homogeneous} and thus $0 \in V$. 
% (And thus Chevalley's original formulation is in fact sufficient for most %applications.)   
\end{remark}

\begin{remark}
The degree bound (\ref{SMALLDEGREE}) in Theorem \ref{WARTHM} is necessary as well as sufficient...
\end{remark}





\\ \\
b)  Division by $\varphi_i(t)$ gives an isomorphism $F[t_i]/\langle \varphi_i \rangle \stackrel{\sim}{\ra} F[t_i]_{\leq d_i}$.  
\[ F[t]/\langle \varphi_1,\ldots,\varphi_n \rangle \cong \left(F[t_1,\ldots,t_{n-1}]/\langle \varphi_1,\ldots,\varphi_{n-1} \rangle \right)[t_n]/\langle \varphi_n \rangle \] \[\cong F[t_1,\ldots,t_{n-1}]/\langle \varphi_1,\ldots,\varphi_{n-1} \rangle 
\otimes_F F[t_n]/ \langle \varphi_n \rangle  \cong \ldots \] \[ \cong F[t_1]/\langle \varphi_1 \rangle \otimes_F \ldots \otimes_F F[t_n]/\langle \varphi_n \rangle \cong \bigotimes_{i=1}^n F[t_i]_{\leq d_i} \cong \mathcal{R}_{\dd}. \]
\\ \\
%We will make use of the following simple results: \\
%(i) If $F$ is a domain and $\varphi(t_1) \in F[t]$ is a monic polynomial 
%of degree $d$, then $F[t_1]/\langle \varphi \rangle$ is a free $F$-module of rank 
%$d_1$.  \\
%(ii) If $F$ is an integral domain and $\varphi_1,\ldots,\varphi_n \in %F[t_1,\ldots,t_n]$, then 
%\[ F[t_1,\ldots,t_n]/\langle \varphi_1,\ldots,\varphi_n \rangle \cong 
%(F[t_1,\ldots,t_{n-1}]/\langle \varphi_1,\ldots,\varphi_{n-1} \rangle)[t_n]/\langle %\varphi_n \rangle. \]
In particular it follows that for all $1 \leq i \leq n$, $F[t_i]/\langle \varphi_i \rangle$ is a free $F$-module of rank $d_i$ and $F[t_1,\ldots,t_n]/\langle \varphi_1,\ldots,\varphi_n \rangle$ is a free $F$-module of rank $d_1 \cdots d_n$.  
Now consider the unique $F$-algebra map $F[t_1] \times \ldots \times F[t_n] \ra F[t]/\langle \varphi_1,\ldots,\varphi_n \rangle$ determined by 
\[ (0,\ldots,t_i,\ldots,0) \mapsto t_i; \]
it factors through 
\[ F[t_1]/\langle \varphi_1 \rangle \times \ldots F[t_n]/\langle \varphi_n \rangle 
\ra F[t]/\langle \varphi_1,\ldots,\varphi_n \rangle. \]
Since this latter map is $F$-multilinear, it induces a map 
\[ \Phi: F[t_1]/\langle \varphi_1 \rangle \otimes_F \ldots \otimes_F F[t_n]/\langle \varphi_n \rangle \ra F[t_1,\ldots,t_n]/\langle \varphi_1,\ldots,\varphi_n \rangle. \]
The map $\Phi$ is visibly surjective, and both its domain and codomain are free $F$-modules of rank $d_1 \cdots d_n$.  












\section{Nullstellensatze Decorticated}

\subsection{Ursitch}
\textbf{} \\ \\ \noindent
Let $\mathcal{R}$ be a binary relation between sets $X$ and $Y$: thus $\mathcal{R} \subset X \times Y$.  We denote by $\mathcal{R}^T$ the dual relation, i.e., 
\[ \mathcal{R}^T = \{ (y,x) \in Y \times X \mid (x,y) \in \mathcal{R}. \]
\\ 
We define $\Phi: 2^X \ra 2^Y$ as follows: for $x \in X$, put 
\[ \Phi(x) = \{y \in Y \mid (x,y) \in \mathcal{R}\}, \]
and for $A \subset X$, put 
\[ \Phi(A) = \bigcap_{x \in A} \Phi(x) = \{y \in Y \mid   \forall x \in A, \ (x,y) \in \mathcal{R} \}. \]
We define $\Psi: 2^Y \ra 2^X$ as follows: for $y \in X$, put 
\[ \Psi(y) = \{x \in X \mid  (x,y) \in \mathcal{R}, \]
and for $B \subset Y$, put 
\[ \Psi(B) = \bigcap_{y \in B} \Phi(y) = \{x \in X \mid \forall y \in B, \  (x,y) \in \mathcal{R}  \}. \]

For $A \subset X$ and $B \subset Y$, we put 
\[\overline{A} = \Psi \Phi A, \ \overline{B} = \Psi \Phi B. \]
Put 
\[ \mathfrak{c}_X = \{ \overline{A} \mid A \subset X\}, \ 
\mathfrak{c}_Y = \{ \overline{B} \mid B \subset Y \}. \]

\begin{remark}(Duality) Note that $\Psi$ is the map $\Phi$ associated to the relation 
$\mathcal{R}^T$. 
\end{remark}

\begin{prop}
\label{GALOISCONNECT}
\label{GALCONNECT}
 Let $\mathcal{R} \subset X \times Y$.  Let 
$A \subset X$, $A_1 \subset A_2 \subset X$, $B \subset Y$, $B_1 \subset B_2 \subset Y$. \\
a) Viewing $2^X$ and $2^Y$ are partially ordered sets under inclusion, the maps $\Phi: 2^X \ra 2^Y$ and $\Psi: 2^Y \ra 2^X$ are \textbf{antitone}: 
\[ \Phi(A_1) \supset \Phi(A_2), \ \Psi(B_1) \supset \Psi(B_2). \] 
b) $A \subset \Psi(B) \iff B \subset \Phi(A)$. \\ 
c) $\Phi(A_1 \cup A_2) = \Phi(A_1) \cap \Phi(A_2)$ and 
$\Psi(B_1 \cup B_2) = \Psi(B_1) \cap \Psi(B_2)$.  \\
d) $\overline{A_1} \subset \overline{A_2}, \ \overline{B_1} \subset \overline{B_2}$.  \\
e) $A \subset \overline{A}, \ B \subset \overline{B}$. \\
f) (Tridempotence) $\Phi A = \Phi \Psi \Phi A = \Phi \overline{A}, \Psi B = \Psi \Phi \Psi B = 
\Psi \overline{B}$, $\Phi A \in \mathfrak{c}_Y, \ \Psi B \in \mathfrak{c}_X$. 
\\
g) $\overline{\overline{A}} = \overline{A}, \ \overline{\overline{B}} = \overline{B}$. \\
h) $\mathfrak{c}_X = \Image \Psi$,  $\mathfrak{c}_Y = \Image \Phi$. \\
i) $\Phi|_{\mathfrak{c}_X}: \mathfrak{c}_X \ra \mathfrak{c}_Y$ and 
$\Psi|_{\mathfrak{c}_Y}: \mathfrak{c}_Y \ra \mathfrak{c}_X$ are mutually inverse bijections.  \\
j) Let $\{A_i\}_{i \in I}$ be a family in $\cc_X$.  Then $\bigcap_{i \in I} A_i 
\in \cc_X$. 

\end{prop}
\begin{proof}
a) If $A_1 \subset A_2$, then 
\[ \Phi(A_1) = \bigcap_{x \in A_1} \Phi(x) \supset \bigcap_{x \in A_2} \Phi(x) = \Phi(A_2). \]
The statement for $\Psi$ follows by duality.  \\
b) Both $A \supset \Psi(B)$ and $B \subset \Phi(A)$  are equivalent to 
\[ \forall x \in A, \ y \in B, \ (x,y) \in \mathcal{R}. \]
c) We have \[\Phi(A_1 \cup A_2) = \bigcap_{x \in A_1 \cup A_2} \Phi(x) = 
\bigcap_{x \in A_1} \Phi(x) \cap \bigcap_{x \in A_2} \Phi(x) = \Phi(A_1) \cap 
\Phi(A_2). \]
The statement for $\Psi$ follows by duality. \\
d) Since $\Phi$ and $\Psi$ are antitone, their compositions $\Psi \Phi$ 
and $\Phi \Psi$ are isotone.  \\
e) The set $\overline{A} = \Psi \Phi A$ consists of all elements $x \in X$ which are 
$\mathcal{R}$-related to every element $y \in Y$ which is $\mathcal{R}$-related to every $x \in A$: the conclusion follows!  The second identity follows by 
duality.  \\
f) The inclusion $\Phi A \subset \Phi \Psi \Phi A$ follows by applying c) 
with $\Phi A$ in place of $B$.  Since $A \subset \Psi \Phi A$ and $\Phi$ is antitone, $\Phi A \supset \Phi \Psi \Phi A$.  This establishes the first identity.  The second follows by duality.  The relations $\Phi A \in \mathfrak{c}_Y, \ \Psi B \in \mathfrak{c}_X$ follow immediately.  \\
g) Let $A \subset X$.  Using tridempotence we get \[\overline{\overline{A}} = \Psi \Phi \Psi \Phi A = \Psi \Phi A = \overline{A}. \]
The second statement follows by duality. \\
h) If $A \subset X$, then by tridempotence $\overline{ \Phi A} = \Phi \Psi \Phi A = \Phi A$, so $\Phi A \in \mathfrak{c}_X$.  If $A \in \mathfrak{c}_X$ then 
$A = \overline{A} = \Psi \Phi A \in \Image \Psi$.  The second statement follows by duality.  \\
i) If $A \in \mathfrak{c}_A$, then $\Psi \Phi A = \overline{A} = A$; 
dually, if $B \in \mathfrak{c}_B$, then $\Phi \Psi B = \overline{B} = B$. \\
j) Put $A = \bigcap_i A_i$.  Then $A \subset A_i$ for all $i \in I$, so 
$\overline{A} \subset \overline{A_i} = A_i$, and thus 
\[ A \subset \overline{A} \subset \bigcap_{i \in I} A_i = A. \]
\end{proof}

\begin{remark}
A \textbf{Galois connection} $(\mathcal{X},\mathcal{Y},\Phi,\Psi)$ between posets $\mathcal{X}$ and $\mathcal{Y}$ is a pair of antitone maps $(\Phi: \mathcal{X} \ra \mathcal{Y}, \Psi: \mathcal{Y} \ra \mathcal{X}$ satisfying 
\[ \forall x \in X, \ y \in Y, \ x \leq \Psi(y) \iff y \leq \Phi(x). \]
Then $(\mathcal{X},\mathcal{Y},\Phi,\Psi)$ is also a Galois connection, the 
\textbf{dual connection}.  
\\ \indent 
Proposition \ref{GALCONNECT}  shows that any binary relation $\mathcal{R} \subset X \times Y$ induces a Galois connection between $2^X$ and $2^Y$.  (It can be shown that every Galois connection between $2^X$ and $2^Y$ 
arises from a unique relation $\mathcal{R}$.)  \\ \indent
 A \textbf{Moore closure operator} on a poset $\mathcal{X}$ is a map $\mathfrak{c}: X \ra X$ satisfying \\
(MC1) For all $x_1 \leq x_2 \in \mathcal{X}$, $\mathfrak{c}(x_1) \leq \mathfrak{c}(x_2)$;  \\
(MC2) For all $x \in \mathcal{X}$, $x \leq \mathfrak{c}(x)$; and \\
(MC3) For all $x \in \mathcal{X}$, $\mathfrak{c}(\mathfrak{c}(x)) = \mathfrak{c}(x)$.  \\
The proof of Proposition \ref{GALCONNECT} works to show that for any Galois connection $(\mathcal{X},\mathcal{Y},\Phi,\Psi)$, $\Psi \circ \Phi$ is a Moore closure operator on $\mathcal{X}$, hence by duality $\Psi \circ \Phi$ is a 
Moore closure operator on $\mathcal{Y}$.  (It can be shown that every Moore closure operator on a poset arises from at least one Galois connection.)  Given a Moore closure operator we define \[\mathfrak{c}_{\mathcal{X}} = \{x \in \mathcal{X} \mid x = \mathfrak{c}(x)\}. \]
Then the proof of Proposition \ref{GALCONNECT} works to show that in any Galois connection $(\mathcal{X},\mathcal{Y},\Phi,\Psi)$, $\Phi$ and $\Psi$ restrict to 
give the \textbf{Galois correspondence}: mutually inverse antitone bijections between $\mathfrak{c}_{\mathcal{X}}$ and $\mathfrak{c}_{\mathcal{Y}}$.  
\end{remark}


\subsection{Stellens\"itche}
\textbf{} \\ \\ \noindent
We consider the following case of the ursitche of the previous section: let $k$ be a commutative ring, and let $X$ be a set.  Let 
\[ k^X = \{ f: X \ra k \}, \]
endowed with the structure of a commutative $k$-algebra under pointwise 
addition and multiplication.  Let $R$ be a $k$-algebra and 
\[ E: R \ra k^X \]
be a $k$-algebra homomorphism.  Let $\ss$ be a subset of $k$.  Let $\mathcal{R} \subset R \times X$ be the relation $\{ (f,x) \mid E(f)(x) \in \ss\}$.  
\\ \\
We denote the operator $\Phi: 2^R \ra 2^X$ by $V$ and the operator $\Psi: 2^X \ra 2^R$ by $I$.  Thus we have corresponding Moore closure operators
\[ J \subset R \mapsto \overline{J} = I(V(J)), \ A \subset X \mapsto 
\overline{A} = V(I(A)). \]

\begin{remark} 
\label{IDEALREMARK}
a) Suppose $\ss$ is closed under addition.  Then so is $I(A)$ for all $A \subset X$.  \\
b) Suppse $\ss$ is an ideal of $k$.  Then: \\
(i) For all $A \subset X$, $I(A)$ is an ideal of $R$.  \\
(ii) For all $J \subset R$, let $\langle J \rangle$ be the ideal generated by $J$.  Then $V(J) = V(\langle J \rangle)$.  \\
c) Suppose $\ss$ is a radical ideal of $k$.  Then so is $I(A)$ for all $A \subset X$.
\end{remark}
\noindent
Because our approach so far has been rather abstract, let us give one example that is simple enough for the reader unfamiliar with Nullstellens\"atze to work out directly but still illustrates some important features of the general case.

\begin{example}
\label{EASYEXAMPLE}
Let $k = \C$ (or any algebraically closed field), $R = k[t]$, $X = k$ and 
$E: k[t] \ra k^k$ be the \textbf{evaluation map} $f \mapsto (x \mapsto f(x))$.  
Then $k[t]$ is a PID, so for every ideal $J \subset k[t]$ we have 
\[V(J) = V(\langle J \rangle) = V( \langle f \rangle) = V(f) \]
for some polynomial $f$ which we can take to be either monic or the zero polynomial.  Let $A \subset k$.  The reader may verify:
\[ \overline{0} = \{0\}. \]
\[ \overline{ (t-x_1)^{a_1} \cdots (t-x_r)^{a_r}} = (t-x_1) \cdots (t-x_r), \]
\[ \overline{A} = \begin{cases} A, & \text{A is finite} \\ k, & \text{A is infinite}. \end{cases}\]
In particular, we find: \\
$\bullet$ If $f \in \overline{J}$, then $f^N \in J$ for some 
$N \in \Z^+$. \\
$\bullet$ The closure operator $A \mapsto \overline{A}$ is \emph{topological}: endowing $k$ with the cofinite topology, for all $A \subset k$ we have 
that $\overline{A}$ is the topological closure of $A$.  \\
$\bullet$ The closure operator $J \mapsto \overline{J}$ is not topological: 
\[\overline{ \langle t \rangle} \cup \overline{ \langle t-1 \rangle} = 
\langle t \rangle \cup \langle t+1 \rangle \subsetneq k = \overline{ \langle t \rangle \cup \langle t+1 \rangle} = \overline{ \langle 1 \rangle} = \langle 1 \rangle. \]
Thus the duality inherent in the ursiche does not exist here.
\end{example}

\begin{lemma}
We place ourselves in the Nullstellensitche with $k$ reduced.  Then: \\
a) $\overline{ \{0\}} = \Ker E$.  \\
b) Thus if $J = \overline{J}$ for every ideal $J$ of $R$, $E$ must be injective. \\
c) For all ideals $J$ of $R$, 
\[ \overline{J} \supset \rad(J+ \Ker E). \]
\end{lemma}
\begin{proof}
a) We have $I(V(0)) = I(X) = \Ker E$.  \\
b) This follows immediately from part a). \\
c) By Remark \ref{IDEALREMARK}c), $\overline{J}$ is a radical ideal; moreover it contains $J$ and $\overline{\{0\}} = \Ker E$.
\end{proof}
 



\subsection{The Zariski Topology}
\textbf{} \\ \\ \noindent
Example \ref{EASYEXAMPLE} suggests that we should try to relate the closure operators in the urNullstellensitch to topological closure operators, but it also shows that in order to do so we need to use more features than those of 
the ursitch.  The following simple result clarifies what we must show.  

\begin{prop} Let $X$ be a set, and let $\cc: 2^X \ra 2^X$ be function.  TFAE: \\
(i) $\cc$ is a \textbf{Kuratowski closure operator}: it is a Moore closure operator and also \\
(KC) $\cc(\varnothing) = \varnothing)$, and for all $A_1,A_2 \subset X$, $\cc(A_1 \cup A_2) = \cc(A_1) \cup 
\cc(A_2)$.  \\
(ii) There is a topology $\tau_X$ on $X$ such that for all $A \subset X$, 
the closure of $A$ with respect to $\tau_X$ -- i.e., the intersection of all 
$\tau_X$-closed subsets containing $A$ -- is $\cc(A)$.
\end{prop}
\begin{proof}
This is entirely straightforward: see e.g. XXX for details.
\end{proof}
\noindent
Let $\tau_X = 2^X \setminus \cc_X$.  For a set $Y$, we denote by 
$(Y,\tau_{\infty})$ the cofinite topology on $Y$.  

\begin{prop}
We place ourselves in the setup of the urstellensitch.  \\
a) Suppose $\ss \subset k$ is a radical ideal.  Then for all $J_1,J_2 \subset R$, 
\[ V(J_1 \cap J_2) = V(J_1 J_2). \]
b) Suppose $\ss \subset k$ is a prime ideal.  Then for all $J_1,J_2 \subset 
R$, 
\[ V(J_1 J_2) = V(J_1) \cup V(J_2). \]
c) If $\ss$ is prime, then $\tau_X$ is a topology on $X$.  \\
d) If $\tau_X$ is a topology on $X$, it is the coarsest topology such that 
for all $f \in R$, $E(f)$ is continuous as a function from $(X,\tau)$ to $(k,\tau_{\infty})$.   
\end{prop}
\begin{proof}
a) Since $J_1 J_2 \subset J_1 \cap J_2$, $V(J_1 \cap J_2) \subset V(J_1 J_2)$.
Conversely, let $x \in V(J_1 J_2)$, and let $f \in J_1 \cap J_2$.  Then 
$f^2 \in J_1 J_2$, so $f(x)^2 \in \ss$; since $\ss$ is radical, $f(x) \in \ss$ 
and thus $x \in V(J_1 \cap J_2)$.  \\
b) Since $J_1 J_2 \subset J_i$ for $i = 1,2$, $V(J_1 J_2) \supset V(J_i)$ 
for $i = 1,2$, thus $V(J_1 J_2) \supset V(J_1) \cup V(J_2)$.  Conversely, 
let $x \in X \setminus V(J_1) \cup V(J_2)$.  Then for $i = 1,2$ there 
is $f_i \in J_i$ with $f_i(x) \notin \ss$.  Since $\ss$ is prime, 
$f_1(x) f_2(x) \notin \ss$, so $x \notin V(J_1 J_2)$.  \\
c) We know that $A \subset X \mapsto V(I(A))$ is a Moore closure operator, so by Proposition X.X it remains to check axiom (KC).  We have 
\[ V(I(\varnothing)) = V(R) = V(1) = \varnothing,\]
and for $A_1,A_2 \subset X$, 
\[ V(I(A_1 \cup A_2)) = V(I(A_1) \cap I(A_2)) = V(I(A_1) I(A_2)) = V(I(A_1)) \cup V(I(A_2)). \]
d) $\ldots$
\end{proof}
\noindent
Henceforth we assume that we are in the Nullstellesitch with $k$ a domain, 
so that Proposition X.X applies.  It is irresistibly tempting to call $\tau_X$ 
the \textbf{Zariski topology} -- so we will do so -- but we warn that in this level of generality the Zariski topology can behave quite differently from 
the most classical and familiar cases.  

\begin{prop}
\label{ZARDISCRETE}
If $E: R \ra k^X$ is surjective, the Zariski topology on $X$ is discrete.
\end{prop}
\begin{proof}
For $A \subset X$, choose $f \in R$ such that $E(f) = 1_{X \setminus A}$.  
Then $f \in I(A)$, so 
\[\overline{A} = V(I(A)) \subset V(f) = \{x \in X \mid E(f)(x) = 0\} = 
\{x \in X \mid 1_{X \setminus A}(x) = 0 \} = A. \]
\end{proof}

\begin{remark}
Let $k_f^X$ be the $k$-subalgebra generated by all characteristic functions $1_A$ for $A \subset X$.  The proof of Proposition \ref{ZARDISCRETE} used only 
the weaker hypothesis that $E(R) \supset k_f^X$.  Clearly $k_f^X$ is proper 
in $k^X$ if and only if $k$ and $X$ are both infinite.  This shows that 
the converse of Proposition \ref{ZARDISCRETE} does not hold.
\end{remark}


\subsection{The Case $R = k^X$}
\textbf{} \\ \\ \noindent
Suppose $k$ is a domain, $R = k^X$ and $E: R \ra k^X$ is the identity map.  Then: \\
$\bullet$ For any $A \subset X$, $I(A) = \langle 1_{X \setminus A} \rangle$ 
is a principal ideal generated by an idempotent element, so \[R = I(A) \times 
I(X \setminus A).\] 
Restricting functions from $X$ to $A$ gives a surjective $k$-algebra homomorphism $k^X \ra k^A$ with kernel $I(A)$, hence 
\[k^X/I(A) \cong k^{A} \]
and $I(A)$ is prime iff $I(A)$ is maximal iff $\# A = 1$. \\
$\bullet$ The Zariski topology on $X$ is discrete: for all $A \subset X$,  \[\overline{A} = V(I(A)) = V(1_{X \setminus A}) = A. \]
$\bullet$ The following are equivalent: \\
(i) $k$ is a field.  \\
(ii) $k^X$ is absolutely flat.  \\
(iii) Every ideal of $k^X$ is a radical ideal.  \\
$\bullet$ The following are equivalent: \\
(i) $k$ is a field and $X$ is finite.  \\
(ii) For all ideals $J$ of $k^X$, $\overline{J} = J$.  

\subsection{Change of Rings}
\textbf{} \\ \\ \noindent
Let $R'$ be a $k$-algebra and $\iota: R' \ra R$ a $k$-algebra homomorphism.  
Then we may define $E' = E \circ \iota$ and consider the Nullstellensiche for 
$(X,R',E')$ alongside that of $(X,R,E)$.  For $I \subset R'$ and $J \subset R$, let 
\[ \iota_*(I) = \langle \{\iota(x) \mid x \in I \} \rangle, \]
\[ \iota^*(J) = \langle \iota^{-1}(J) \rangle. \]
One immediately checks that
\begin{equation}
\label{PULLPUSHEQ}
\iota_* \iota^* J \subset J,
\end{equation}
\begin{equation}
\label{PUSHPULLEQ}
\iota^* \iota_* I \supset I.
\end{equation}
For $A \subset X$, put 
\[I'(A) = \{f \in R' \mid \forall a \in A, \ E(\iota(f))(a) = 0\}. \]
Then for all $J \subset R'$ and $A \subset X$, we have 
\[ V(J) = V(\iota_* J), \]
\[ I'(A) = \iota^* I(A). \]
It follows that for all $J \subset R'$, 
\[ \overline{J} = I' V J = I' V \iota_* J = \iota^* I V \iota_* J = 
\iota^* \overline{\iota_* J}. \]
Since $\overline{A}$ is now ambiguous, we introduce more notation: for $A \subset X$, write 
\[ c(A) = V(I(A)), \ c'(A) = V(I'(A)). \]
Now for all $A \subset X$, we have 
\[ c'(A) = V(I'(A)) = V(\iota^* I(A)) = V(\iota_* \iota^* I(A)) \supset 
V(I(A)) = c(A). \]
We immediately deduce the following result.

\begin{prop}
\label{COARSERPROP}
In the above setup, let $\tau_X$ denote the Zariski topology on $X$ 
with respect to $E: R \ra k^X$ and $\tau'_X$ denote the Zariski topology 
on $X$ with respect to $E' = E \circ \iota: R' \ra k^X$.  Then: \\
a) $\tau'_X$ is coarser than $\tau_X$.  \\
b) If $\tau_X$ is quasi-compact (resp. Noetherian), so is $\tau_X'$. \\
c) If $\tau'_X$ is Kolmogorov, separated or Hausdorff, so is $\tau_X$.
\end{prop}




\section{Restricted Variables}
\noindent
Let $k$ be a domain, let $n \in \Z^+$, let $R = k[t] = k[t_1,\ldots,t_n]$, 
and let $X \subset k^n$.  Let $E_X = E: R \ra A$ be the \textbf{evaluation map} 
$f \in k[t] \mapsto (x \in X \mapsto f(x))$.  For $J \subset k[t]$ we write 
\[ V(J) = \{x \in k^n \mid \forall f \in J, \ f(x) = 0\} \]
and 
\[ V_X(J) = \{x \in X \mid \forall f \in J, \ f(x) = 0\}, \]
so $V_X(J) = V(J) \cap X$.  

\subsection{The Zariski Topology}

\begin{lemma}
\label{ZTT1}
The Zariski topology $\tau_X$ on $X$ coincides with the topology induced by the Zariski topology on $k^n$ on the subset $X$.
\end{lemma}
\begin{proof}
This follows almost immediately from the identity $V_X(J) = V(J) \cap X$; 
the details may safely be left to the reader.
\end{proof}



\begin{lemma}
\label{ZTT2}
Let $x = (x_1,\ldots,x_n) \in X$.  Put $\mm_x = \langle t_1-x_1,\ldots,t_n - x-n \rangle$.  Then: \\
a) We have $I(x) = \mm_x$.  \\
b) We have $\overline{ \{x\}} = \{x\}$. \\
c) The map $(X,\tau_X) \ra \Spec k[t], \ x \mapsto \mm_x$ is an embedding of 
topological spaces.
\end{lemma}
\begin{proof}
a) Clearly $t_i-x_i \in I(x)$ for all $1 \leq i \leq n$ and thus $\mm_x \subset I(x)$.  Conversely, the map $E_x$ which evaluates $f \in k[t]$ at $x$ gives a surjective homomorphism $k[t] \ra k$ with kernel $I(x)$.  Since also $k[t]/\mm = k$, we must have $I(x) = \mm_x$.  \\
b) We have $\overline{ \{x\}} = V(I(x)) = V(\mm_x)$.  If $y = (y_1,\ldots,y_n) \neq x$, then $y_i \neq x_i$ for at least one $i$ and then $t_i - x_i \in \mm_x$ and does not vanish at $y$.  So $V(\mm_x) = \{x\}$.  \\
c) $\ldots$
\end{proof}




\begin{thm} 
Let $\tau_X$ denote the Zariski topology on $X \subset k^n$.  \\
a) $\tau_X$ is separated.  \\
b) $\tau_X$ is Noetherian.  \\
c) The following are equivalent: \\
(i) $\tau_X$ is discrete.  \\
(ii) $X$ is finite.  
\end{thm}
\begin{proof}
a) Lemma \ref{ZTT2}b) shows that points are closed. \\
b) Let $K$ be the fraction field of $k$, $R = K[t]$, $R' = k[t]$ and $\iota: R' \ra R$ the natural embedding.  Then $X \subset k^n \subset K^n$, and by Proposition \ref{COARSERPROP}, the Zariski topology on $X$ induced by $R'$ is coarser 
than the Zariski topology on $X$ induced by $R$.  By Lemma \ref{ZTT2}c), the Zariski topology 
on $X$ induced by $K$ is homeomorphic to a subspace of $\Spec K[t]$.  Since $K[t]$ is a Noetherian ring, $\Spec K[t]$ is a Noetherian space, and thus 
so is every subspace.  \\
c) We now know that $\tau_X$ is quasi-compact and separated.  Any quasi-compact 
discrete space is finite, and any finite separated space is discrete.
\end{proof}










 
\subsection{Effectivity in the non-Cylindrical Case}
\textbf{} \\ \\ \noindent
Let $F$ be a field, and let $g_1,\ldots,g_m \in F[t]$.  Let $X \subset F^n$ be finite, and write out some finite generating set $I(X) = \langle \psi_1,\ldots,\psi_N \rangle$.   The Finitely Restricted Nullstellensatz asserts that if $f \in F[t]$ vanishes at all $x \in X$ 
at which $g_1,\ldots,g_m$ vanish, then there are $q_1,\ldots,q_m,j_1,\ldots,j_N \in F[t]$ such that 
\[ f= \sum_{i=1}^m h_i g_i + \sum_{i=1}^N j_i \psi_i. \]
It would be nice to make this result \textbf{effective} by giving degree bounds 
on the $h_i$'s and $j_i$'s, as was done in the cylindrical case.  To do this in a nice way, one should choose the $\psi_i$'s to be as nice as possible.  Our description of $I(X)$ allows us to write down an explicit set of generators, namely
\[ \ldots \]
\[ \ldots \]
However, this generating set, though ``explicit'', does not seem to be of much use: 
for instance, in the cylindrical case it does not seem straightforward to use this description of $I(X)$ to show that it is also generated by $\varphi_1,\ldots,\varphi_n$.  
\\ \\
In the cylindrical case one can make precise the ``niceness'' of the generators $\varphi_1,\ldots,\varphi_n$ using the notion of a universal Gr\"obner basis.  This suggests that Gr\"obner basis techniques ought to be useful in the general case as well.

\subsection{Further Directions}
\textbf{} \\ \\ \noindent
If $X \subset F^n$ is such that $I(V_X(J)) = J + I(X)$ for all ideals $J$, then $X$ 
is necessarily finite.  Indeed the above condition implies that every ideal of the ring $F[t]/I(X)$ is a radical ideal.  For a Noetherian commutative ring $R$, the property that every ideal is radical is equivalent to absolute flatness and also to semisimplicity: in other words, $F[t]/I(X)$ must be a finite product of fields.  In particular, $F[t]/I(X)$ must have finitely many prime ideals, whereas if $X$ is infinite then $\{ \mm_x \mid x \in X\}$ is an infinite set of prime ideals of $F[t]/I(X)$.  
\\ \\
If $X$ is infinite, then $\overline{X} = V_{F^n}(I(X))$ is an affine algebraic $F$-variety of positive dimension, with coordinate ring $F[t]/I(X)$.  Thus a restricted Nullstellensatz in this case amounts to a description of the connection between algebraic functions and $F$-rational points on $\overline{X}$.  This is certainly possible in some cases, e.g. when $\overline{X}$ is a nonsingular curve 
as then $F[t]/I(X)$ is a principal ideal domain.  
\\ \\
Restricted Nullstellens\"atze are compatible with restriction: i.e., if $Y \subset X$, then $V_Y \circ I$ can be completely understood in terms of $V_X \circ I$.  In particular, when $F$ is algebraically closed, then for all $X \subset F^n$ and $J \subset F[t]$ we have 
\[ I(V_X(J)) = \rad J + I(X). \]




%so $I(V_X(J)) = J+I(X)$.  
%
%between two finite sets each of cardinality $2^{\# X}$. 
%It f
%\[ I(A) = I(\bigcup_i \{x_i\}) = \bigcap_i I(x_i) = \bigcap_i \mm_{x_i} = %\prod_{i=1}^k \mm_{x_i}, \]
%the last equality by the Chinese Remainder theorem.  By Lemma \ref{FRNALEMMA}b),
%\[ V_X(I(A)) = V_X(\prod_{i=1}^k \mm_{x_i}) = \bigcup_{i=1}^k V_X(\mm_{x_i}) = %\bigcup_{i=1}^k \{x_i\} =  A. \]
%Thus $I: 2^X \ra 2^{F[t]}$ is injective.  Since its image consists 
%of ideals of $F[t]$ containing $I(X)$, there are thus at least $2^{\# X}$ 
%ideals of $F[t]/I(X)$.  On the other hand, by Proposition \ref{EVALSURJ} the %evaluation map induces an isomorphism $F[t]/I(X) \stackrel{\sim}{\ra} F^X$.  Since %every ideal of a finite product of rings is a product of ideals in the factor rings %and the field $F$ has two ideals, this shows that $F[t]/I(X)$ has precisely $2^{\# %X}$ ideals.  It follows that every ideal $J$ of $F[t]$ which contains $I(X)$ is of 
%the form $I(A)$ for a unique $A \subset X$, and if $J = I(A)$, then by Lemma %\ref{FRNALEMMA}a),
%\[ I(V_X(J)) = I(V_X(I(A))) = I(A), \]
%so $J = I(V_X(J))$.  Finally, if $J$ is any ideal of $F[t]$, then 
%\begin{equation}
%\label{ATLAST}
% I(V_X(J)) \subset I(V_X(J+I(X))) = J + I(X). 
%\end{equation}
%Combining (\ref{LOWERBOUNDEQ}) and (\ref{ATLAST}), we get 
%\[ I(V_X(J)) = J + I(X). \]


\subsection{The Chevalley-Alon-Tarsi Lemma}
\textbf{} \\ \\ \noindent
Our proof of the Finitely Restricted Nullstellensatz is set up so as to maximally exploit the following truly basic principle -- for a map between two sets of 
equal finite cardinality, injectivity, surjectivity and bijectivity are all equivalent -- as well as its analogue in linear algebra: for a linear map between two vector spaces of equal finite dimension, injectivity, surjectivity 
and bijectivity are all equivalent. \\ \indent  
These principles guarantee the existence of multiple approaches to the Combinatorial Nullstellensatz and related topics.  The traditional approach concentrates on injectivity by first establishing the following simple result.

\begin{lemma}(Chevalley-Alon-Tarsi)
\label{CATLEMMA}
Let $F$ be a domain, $n \in \Z^+$, and $f(t) \in F[t] = k[t_1,\ldots,t_n]$; for $1 \leq i \le n$, let $d_i$ be the $t_i$-degree of $f$, let $X_i$ be a subset of $F$ with $\# X_i > d_i$, and let $X = \prod_{i=1}^n X_i$.  If $f(x) = 0$ for all $x \in X$, then $f = 0$.   
\end{lemma}
\noindent
However in our approach Lemma \ref{CATLEMMA} comes out last, by combining Proposition \ref{CYLINDRICALREDUCTION} with Theorem \ref{FRN}b).  We structure things this way because Lemma \ref{CATLEMMA} 
is particular to the cylindrical case $X = \prod_{i=1}^n X_i$ and we want to deal 
with a general finite subset.  
\\ \\
Although Chevalley's work used Lemma \ref{CATLEMMA}, \emph{the} key step in the proof of Chevalley's Theorem is the explicit polynomial formula (\ref{DELTAFUNCTION}) for the characteristic function (on $\F_q^n$) of a point.  Thus Chevalley does all the work necessary to show that 
\[E_{\F_q^n}: \F_q[t] \ra \F_q^{\F_q^n}, f \mapsto (x \mapsto f(x)) \]
is surjective.  Since $\F_q^{\F_q^n}$ and the set of all $(q,\ldots,q)$-reduced 
polynomials each have cardinality $q^{q^n}$, the surjectivity 
of $E_{\F_q^n}$ together with the existence of the reduced polynomial (established by repeated substitutions $t_i^q \mapsto t_i$) already implies the uniqueness of the reduced polynomial, so in a sense he was working too hard.%\footnote{I noticed this in 2008 while writing lecture notes for a number %theory course.}











































section{Comments on Prior and Further Work}

\subsection{The Finite Field Nullstellensatz}
\textbf{} \\ \\ \noindent
As mentioned above, in \cite{Chevalley35}, Chevalley proves 
\begin{equation}
\label{WEAKFFNULL}
 I(\F_q^n) = \langle t_1^q - t_1,\ldots,t_n^q -t_n \rangle, 
\end{equation}
which is the Combinatorial Nullstellensatz I in the case $F = X_1 = \ldots = X_N = \F_q$ of Theorem \ref{FRN}b).  As we've seen, to get from this to Corollary \ref{FFN} is short and elementary.  It seems almost surprising that Corollary \ref{FFN} -- the \textbf{Finite Field Nullstellensatz} -- does not already occur in Chevalley's paper.  
%\\ \\
Rather it was first established in a 1966 \emph{Comptes Rendus} note of G. Terjanian \cite{Terjanian66}, communicated by Chevalley.  However this work of Terjanian seems to have been almost forgotten: it has (as yet) no citations on MathSciNet.\footnote{I encountered \cite{Terjanian66} 
only after the first draft of the present note was completed, in the context of a 
literature search on generalizations of Chevalley's Theorem.}  Corollary \ref{FFN} was obtained independently 
in 1991 by R. Germundsson \cite{Germundsson91} (in the case of prime order fields).  It was also treated (for arbitrary finite fields, and with a different proof) in the master's thesis of S. Gao \cite{Gao09}.
\\ \\
There are many commonalities between the proof of Theorem \ref{MAINTHM}a) 
and Terjanian's proof of the Finite Field Nullstellensatz (which he attributes  to J.-P. Serre).  Terjanian uses Chevalley's Lemma (Lemma \ref{CATLEMMA} with $F = X_1 = \ldots = X_n = \F_q$) and the surjectivity of the evaluation map in place of the Chinese Remainder Theorem and thus seems in spirit a bit more reliant on the cylindrical structure (although we feel honorbound to point out that Terjanian's method can equally well be used to prove Theorem \ref{MAINTHM}a)).  As befitting a \emph{Comptes Rendus} note, his treatment is rather brief: he establishes the isomorphism $\F_q[t_1,\ldots,t_n]/\langle t_1^{q}-t_1,\ldots,t_n^{q}-t_n \rangle \stackrel{\sim}{\ra} \F_q^{\F_q^n}$, 
observes that the ideals in $\F_q^{\F_q^n}$ are all generated by characteristic functions of subsets, and leaves the reader to deduce the result from this.  
\\ \\
In comparison, the arguments of Germundsson and Gao seem considerably more complicated.  Germundsson's proof of 
the Finite Field Nullstellensatz establishes that every ideal $J$ of $\F_q[t]$ containing $I(\F_q^n) = \langle t_1^{q}-t_1,\ldots,t_n^{q}-t_n \rangle$ is a radical ideal as follows: since $q \geq 2$, it suffices to show that if $f \in F[t]$ and $f^q \in J$, then $f \in J$.  But if $f^q \in J$, then since $f^q-f \in I(\F_q^n) \subset J$, indeed $f \in J$.  He next shows by a short, elementary argument that the prime ideals of $\F_q[t]/I(\F_q^n)$ are precisely $\mm_{x}$ for $x \in \F_q^n$, and then invokes the Primary Decomposition Theorem to write every (radical) ideal of $\F_q[t]/I(\F_q^n)$ as a finite intersection of prime ideals.  Finally, using the formal 
properties of $I$ and $V_{\F_q^n}$ he easily establishes the result for ideals $J$ of the form $\bigcap_i I(\mm_{x_i})$ (this is essentially what we did at the end of the proof of Theorem \ref{FRN}a)).  Some finite field arithmetic 
is used, but not essentially: after Alon, one can see that Germundsson's method would work to prove Theorem \ref{FRN} in the cylindrical case. 
\\ \\
A faster way to deduce Corollary \ref{FFN} from (\ref{WEAKFFNULL}) and from the fact that all ideals of $\F_q[t]/I(\F_q^n)$ are radical 
appears in the master's thesis of S. Gao.  Interestingly, Gao uses a \emph{strengthening} of Hilbert's Nullstellensatz which appears in \cite{Lang}.
%\footnote{Gao also shows how to deduce Theorem \ref{SEMIN} from Hilbert's %Nullstellensatz, whereas Lang proceeds from scratch and gives an argument proof %that is a bit more elaborate than the usual proofs of Hilbert's %Nullstellensatz.}

\begin{thm}(Semirational Nullstellensatz)
\label{SEMIN}
Let $F$ be a field, with algebraic closure $\overline{F}$. For an ideal $J$ of $F[t_1,\ldots,t_n]$, let 
\[V^a(J) = \{x \in \overline{F}^n \mid \forall g \in J, \ g(x) = 0\}. \] For $S \subset \overline{F}^n$, let
\[ I(S) = \{ g \in F[t] \mid \forall x \in S, \ g(x) = 0\}. \]
 Then for all ideals $J$ of $k[t_1,\ldots,t_n]$, we have $I(V^a(J)) = \rad J$.  
\end{thm}
\noindent
The ideal $I(\F_q^n)$ is ``rational'' in the sense that \[V^a(I(\F_q^n)) = V_{\F_q^n}(I(\F_q^n)) = \F_q^n.\]  
Using this, the derivation then proceeds as follows:
\[ I(V_{\F_q^n}(J)) = I(V^a(J) \cap \F_q^n) = I(V^a(J) \cap V^a(I(\F_q^n)))  = I(V^a(J \cup I(\F_q^n)) \] \[= I(V^a(J+I(\F_q^n))) = \rad (J+I(\F_q^n)) =  J + I(\F_q^n). \]
This method also works to prove the cylindrical case of Theorem \ref{FRN}.  

\subsection{Multisets}
\textbf{} \\ \\ \noindent
Among the deluge of recent work on the Combinatorial Nullstellensatz, the ones which 
seem closest in spirit to the present note are \cite{KMR11} and \cite{KR12}. 
\\ \\
In \cite{KMR11} it is shown that Corollary \ref{PM} and portions of Proposition \ref{CYLINDRICALREDUCTION} can be appropriately generalized so as to work over any commutative ring $F$.  We have not pursued that direction here because it seems that we would be leaving behind all connections with geometry: $V_A(J)$ need no longer be a radical ideal, the map $A \subset X \mapsto V_X(I(A))$ need not be a Kuratowski closure operator (i.e., need not induce a topology on $X$), and there seems little hope of attaining a Nullstellensatz.  
\\ \\
More pertinently, \cite{KMR11} and \cite{KR12} also treat nonsquarefree polynomials 
\[ \varphi_i(t_i) = \prod_{x_i \in X_i} (t_i-x_i)^{m_i}. \]
When $\max m_i > 1$, $\Phi = \langle \varphi_1,\ldots,\varphi_n \rangle$
is no longer a radical ideal; equivalently 
\[ F[t]/\Phi \cong \bigotimes_{i=1}^n F[t_1]/\langle t_1^{m_i} \rangle \]
is a non-reduced ring.  Proposition \ref{CYLINDRICALREDUCTION} on Cylindrical Reduction still applies, but $\Phi$ is no longer the ideal of functions vanishing on a finite 
subset, so the problem is to usefully interpret the hypothesis $f \in \Phi$ in this context.  The authors solve this problem very nicely by giving an interpretation in terms of vanishing coefficients of the Taylor series expansion of $f$ at $(x_1,\ldots,x_n)$.  Their approach is especially appealing and useful from the perspective of combinatorial applications.    
\\ \\
It would be interesting to explore simultaneous generalizations of these works and the present work, e.g. by considering the ideals corresponding to non-cylindrical multisets, in particular products of not necessarily distinct maximal ideals $\mm_{x}$ of points $x \in F^n$.  It is also an interesting challenge to fashion a  Nullstellensatz here: the usual Nullstellensatz setup inherently 
ignores multiplicities, but ``Nullstellens\"atze with nilpotents'' are not absolutely unheard of: e.g. \cite{EH79}.
\\ \\
Having entertained the idea of polynomials $\varphi_i$ which are split but not squarefree, it is natural to think about the case where $\varphi_i$ is an arbitrary monic polynomial: i.e., possibly with irreducible factors of degree greater than $1$.  If $\varphi(t_i)$ has no roots in $F$, then $I(V_X(\varphi(t_i))) = 
I(\varnothing) = F[t]$....if $X$ is taken to be a subset of $F^n$.  However in the Semirational Nullstellensatz we saw that it can be profitable to extend ground field $F$ ``on the geometric side''.  One can pursue Nullstelles\"atze in the setting where $K/F$ is an extension of integral domains and $X \subset K^n$.  There is still an induced topology on $X$, which is always Noetherian but need not satisfy even Kolmogorov's ``$T_0$'' separation axiom.  In this context the description of the topological closure operation involves Galois theory and transcendence degrees.
\\ \\
Incorporating some handwritten notes from winter break 2013-2014: 
\\ \\
This in the context of the $K/k$ Nullstellensatz for an arbitrary field extension $K/k$.  
\\ \\
$\bullet$ For $S \subset K^n$, $\overline{S}$ is $\Aut(K/k)$-invariant. \\
(The notes included a proof, which is easily recovered.)
\\ \\
$\bullet$ When $K = \overline{k}$, it looks like for all $S \subset K^n$, $\overline{S}$
 is the $G$-orbit of the usual Zariski closure, which is a finite union of sets 
$\sigma \tilde{S}$ for $\sigma \in \Aut(K/k)$ and $\tilde{S}$ the classical Zariski closure.
\\ \\
We have 
\[ \overline{S}= V_K( I_k(S)) = V_K( I_k(S)_*). \]
Thus $tau_{K/k}$ is a coarsening of $\tau_k$: the closed sets are precisely the zero sets 
of ideals which are extended from $k$.  This influences the $G$-equivariance property but 
in general is much stronger.  In particular, $\tau_{K/k}$ is always a Noetherian topology.
\\ \\
If $K/k$ is finite, what does this have to do with $I^*$ and the nom map??  E.g. $n = 1$, $s \in K$.  Then $I_K\{s\} = minpoly(s) = P_s(t)$, so $\overline{s} = V_K P_s(t) = $ the set 
of distinct roots of $P_s(t)$ in $K$.  So:
\\ \\
$\bullet$ If $K/k$ is Galois, $\# \overline(s) = [k(s):k] = G(s)$.
\\ \\
$\bullet$ If $K/k$ is normal, then $\# \overline{s} = [k(s):k]_{\sep}$.  
\\ \\
$\bullet$ If $K/k$ is not normal, then there is $p \in k[t]$ irreducible of degree 
$d > 1$ and $s \in K$ such that $p(s) = 0$ but $p$ does not split in $K$.
\\ \\
If $K/k$ is infinite algebraic, same story.
\\ \\
Edxample: $\R/\Q$ $G = \{1\}$, $s$ totally real. 

















\subsection{From Chevalley to Alon}
\textbf{} \\ \\ \noindent
The first application of CNII in \cite{Alon99} is to Chevalley's Theorem.  But there is a tighter relationship: the technique Alon uses to prove CNI directly generalizes the technique that Chevalley used, a process which we call \textbf{cylindrical reduction}. 
% (This is not mentioned in \cite{Alon99}, and it seems likely that he independently %rediscovered Chevalley's technique in a more general form.)
Chevalley applies (his special case of) CNI to prove his theorem in a different way from Alon's deduction of CNII: whereas Alon uses Theorem \ref{CN}b), Chevalley gives an explicit formula for a reduced polynomial in terms of its associated polynomial function.  This \textbf{Atomic Formula} easily implies the Coefficient Formula, which in turn immediately implies CNII.  Moreover, since the spirit of CNII is to deduce information about the coefficients of a polynomial 
from information about its values on a finite set, the Atomic Formula is really the natural result along these lines, as it literally recovers the polynomial 
from its values on a sufficiently large finite set.  Thus we feel that researchers should have the Atomic Formula in their toolkits.
%With regard to the Coefficient Formula and the Atomic Formula: one might reasonably %suspect that such polishings of Alon's results contribute little of real value.  %However, to borrow Wigner's famous phrasing, the \emph{unreasonable effectiveness} %of polynomial methods in solving problems has been amply demonstrated: for such a %powerful tool, seemingly minor improvements can have important 
%consequences.  Thus the recent emphasis on the Coefficient Formula seems justified.  %Similarly we feel that researchers should have the Atomic Formula in their %toolkits.
%\\ \\
%Our Atomic Formula is one of the ``interpolation formulas'' of a 2008 work of U. Schauz %\cite[Thm. 2.5]{Schauz08a}.  Unfortunately it seems that Schauz's work has not been %properly appreciated. 
% 
%Thus in this section we attempt to present this material in a way which reveals it to %be as simple and appealing as Chevalley's classic work.