In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity. 


What's the current status in mathematics/computer science of this infinite combinatorial optimization problem?


Given an interaction range $k+1$, and interaction parameters $v\_0,v\_1,\ldots,v\_k$,
$$
\inf\_{\sigma \in S} \left( \lim\_{N \rightarrow \infty} \frac{1}{N} \sum\_{ i \in \{-N,\ldots,N\} } \left( v\_0 \sigma\_i + \sum\_{ j \in \{1,\ldots,k\} } v\_j \sigma\_i \sigma\_{i + j} \right) \right)
$$
where the minimization is over the subset $S$ of $\{0,1\}^{\Bbb Z}$ consisting of all $\sigma \in \{0,1\}^{\Bbb Z}$ for which the above limit exists.


The physical intuition is that each atom can be in 2 spin states, 0 or 1, and they have interactions defined by $v\_0$,...,$v\_k$. We want to find the ground state of the system.


I currently have an algorithm and code that could compute on a personal computer for k<~25 and I am planning for a publication on it. Further, if you are also interested in this kind of problem (2D, 3D or even higher dimension) and want to collaborate. Please don't hesitate to contact me:) Thank you. 



Combinatorial optimization problem involving infinite spin system
There is one framework in the literature that maybe useful in your problem, depending on the larger context of the question.


In the **supernumber** framework your question (1) is actually a lower dimensional problem than typically encountered in quantum field theories, the usual places you find supernumbers. 


( The typical case is one that involves transformations (including division by $n$) of (where necessary) infinite sums of objects $c\_{1,2,...,n}\cdot\sigma^n\cdot\sigma^{n-1}\cdot\,... \cdot\sigma^1$ for $n\rightarrow\infty$, including *every* smaller permutation, such as $c\_{1,2,3,4}\cdot\sigma^4\cdot\sigma^3\cdot\sigma^2\cdot\sigma^1$. ) 



> 
> B. DeWitt, 1992, *Supermanifolds*, Cambridge University Press, nicely gives the tools required, the supernumber calculus. You would be interested in pp.1-13,37-46.
> 
> 
> 


It is intuition but I suspect that bounds for your system can be found algebraically in each case (determined by values of k, and v0,v1, v2, ...) by putting it into supernumber form (even supernumbers are commuting, odd supernumbers are anticommuting) and taking appropriate integrals. The fact that transformations (functions...) of supernumbers integrated need not be analytic, merely a distribution, allows combinatorics to be represented easily in calculus...


The result and part of the method in detail I think would then mostly depend on the precise global conditions that bound the interaction parameters in whatever way they are systematically bounded in the overall problem (so I agree the problem is not generally decidable).


