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.

Improve this question
$\endgroup$
6
  • $\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
    Commented Oct 5, 2014 at 20:14
  • $\begingroup$ It should be latter: the S version:) Thank you for your rigorous analyzing of my problem:) $\endgroup$
    – user40780
    Commented Oct 5, 2014 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
    Commented Oct 5, 2014 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
    Commented Oct 5, 2014 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
    Commented Oct 5, 2014 at 21:30

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
2
  • $\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
    Commented Oct 6, 2014 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
    Commented Oct 6, 2014 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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Oct 5, 2014 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
    Commented Oct 5, 2014 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.