2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Should the lim be replaced with limsup? $\;\;\;$ If no, should $S$ be defined as $\{\phi \in \{\hspace{-0.02 in}0\hspace{.02 in},\hspace{-0.04 in}1\hspace{-0.03 in}\}^{\mathbb Z} : \text{ the following limit exists}\}\:$ and $\:\{\hspace{-0.02 in}0\hspace{.02 in},\hspace{-0.04 in}1\hspace{-0.03 in}\}^{\hspace{-0.02 in}\mathbb Z}\:$ be replaced with $S\hspace{.02 in}$? $\hspace{1.7 in}$ $\endgroup$ – user5810 Oct 5 '14 at 20:14
  • $\begingroup$ It should be latter: the S version:) Thank you for your rigorous analyzing of my problem:) $\endgroup$ – user40780 Oct 5 '14 at 20:17
  • 1
    $\begingroup$ I am also doing materials science research at the moment :) I remember 5 references which might be useful to you, two from pure physics, two from continuum mechanics, one older mathematical article which has been getting more attention the last several years. Would you like the references or a brief summary of the results? (I'll check first if my memory is correct and they treat precisely this problem or something similar yet different in some important way that make their results inapplicable. The physics works discuss a supermanifolds context.) $\endgroup$ – Gottfried William Oct 5 '14 at 20:50
  • $\begingroup$ Thank you sooo much:) I would greatly appreciate it if you could post the reference :) If you have the brief summary of the result, then it would be super great because sometimes it is hard to read into one paper in different field. Any help is very appreciated:) $\endgroup$ – user40780 Oct 5 '14 at 21:02
  • $\begingroup$ @GuidoJorg: Further, if you are also interested in this problem? We might possibly collaborate and work out some more papers together?:) $\endgroup$ – user40780 Oct 5 '14 at 21:30
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ IIRC Onsager's original solution of the 2D Ising model relied on Clifford algebra--is what you're saying above related to this observation? $\endgroup$ – Steve Huntsman Oct 6 '14 at 0:36
  • $\begingroup$ supernumber construction relies on Grassmann algebra, but this of course can be related in a systematic way to a corresponding Clifford algebra that imposed additional constraints. $\endgroup$ – Gottfried William Oct 6 '14 at 0:44
1
$\begingroup$

In dimension $1$ this can be reduced to a finite (though perhaps very large) computation. In higher dimensions the problem is more difficult and more interesting. I'm not sure if it is even decidable: there are quite similar problems (such as the Domino Problem) that are not.

$\endgroup$
  • $\begingroup$ Actually, it is undecidable. But algorithmically, I have invented ways to compute upper bound and lower of the objective value. In material science, we could show that if the optimal function is periodic (which is usually the case ), we could have algorithms to prove and search ground states for arbitrarily small epsilon. I am actually working on this paper. $\endgroup$ – user40780 Oct 5 '14 at 22:07
  • $\begingroup$ If you are interested, I could keep you updated with our latest research and have possible further collaboration together? $\endgroup$ – user40780 Oct 5 '14 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.