I apologise if this is a duplicate in any way or is off topic.
Given a (finite) set $S$ of $n$-tuples of real numbers, is there an interpolation polynomial that goes through each $s\in S$?
Motivation.
A common type of problem found on social media is to infer a pattern from a list of triples, usually in the form of a few evaluations of a binary operation, then apply that pattern to a couple. For instance,
If
- $2+3=10,$
- $7+2=63,$
- $6+5=66,$
then what is $11+12$?
The intended answer is presumably $253$; the pattern you're supposed to infer is "$a+b=a(a+b)$".
It is my suspicion that the answer could be anything with enough imagination or, indeed, something akin to an interpolation polynomial.
For each $s = (s_1, \dots, s_{n-1}, s_n) \in S$, define the following polynomial: $$f_s = (x_1 - s_1)^2 + \dots + (x_{n-1} - s_{n-1})^2.$$ Then let $$f = \sum_{s \in S} s_n \prod_{s' \ne s} \frac{f_{s'}}{f_{s'}(s_1, \dots, s_{n-1})}.$$ You'll now have $f(s_1, \dots, s_{n-1}) = s_n$. The idea is simply to generalise the factors $x - s$ in usual Lagrange interpolation to these functions $f_s$, which are chosen to be zero precisely at the point $s$.