Nonstandard State ˊ_>ˋ

A nonogram inside a nanoparticle......

Take a platinum–nickel nanoparticle of about ten thousand atoms. I can write down two different ways to place the nickel atoms in it. If you photograph both versions along the three crystal axes, the photos agree exactly, as every column of atoms contains the same number of nickel atoms in both. Yet if you are curious about which of two surface platinum atoms grabs a hydroxyl group (OH) more tightly, the two versions give opposite answers. This matters because particles like this are catalysts in hydrogen fuel cells, and how tightly a surface atom binds OH is a standard proxy for how active it is. So the question behind this post is simple to state: how many photos do you need before you can trust a claim about which surface atoms are the good ones?

( ´ ▽ ` )ノ The short answer is that it depends heavily on the particle. For one particle, three photos already settle most questions and a fourth settles all of them. For another, three photos leave most surface atoms uncertain by more than the chemistry model's own error bar, and simple deduction from a fourth photo pins down only a few hundred more of its atoms.

The data come from a 2024 study by Yang and colleagues in Nature Catalysis. They photographed single Pt–Ni nanoparticles in an electron microscope from more than fifty angles and reconstructed the position and element of every atom. They also made all of it public: coordinates, element labels, the processed photos, and the formula they used to estimate how strongly each surface platinum atom binds OH. Here is the puzzle I built from that data. Take the reconstructed particle and keep the positions, but forget which atoms are nickel and which are platinum. Now imagine an ideal photo taken straight down one of the crystal axes. Each atom column shows up as a single spot, and the photo tells you how many nickel atoms sit in that column. It does not tell you which ones. If you know nonograms, this is a three-dimensional one. In a nonogram you get the number of filled squares in every row and column and must work out the picture. Here the particle is a box of a few thousand balls, each either platinum or nickel. Every photo gives you one set of line counts, and the question is how many colorings of the balls agree with all the counts you have.

If only one coloring fits, the photos determine the particle. If several fit, everything that differs between them is uncertain, including how many nickel neighbors a given platinum atom has.

With two photos along two axes, the puzzle falls apart into flat slices. Each slice is an ordinary grid of zeros and ones with known row and column totals. That problem has been understood since the 1950s, and a computer solves it quickly. With three photos, the general problem is NP-hard. Gardner, Gritzmann and Prangenberg proved this in 1999, motivated by exactly this kind of electron microscopy. Hard here means that no known method handles every instance quickly, so some puzzles could take astronomically long. The worst case is not the whole story, though, and the useful question is where the hardness actually lives. Start with the obvious deductions. If a column still needs zero nickel atoms, every undecided ball in it is platinum. If it needs as many nickel atoms as it has undecided balls, they are all nickel. Each deduction can unlock others, so you repeat until nothing changes. Now look at what is left. Suppose a column has exactly two undecided balls and still needs one nickel atom. That column is a switch: one ball is nickel and the other is platinum, and you just don't know which. Switches link up through shared balls into chains. Flip one switch and the whole chain flips with it, like a row of dominoes. If every column had at most two undecided balls, the puzzle would just be a set of independent chains, each with two settings. That is easy to work with. Chains even give clean answers about chemistry. We can suppose a platinum atom has two neighbors in the same chain, and they always take opposite colors. Then exactly one of them is nickel, whichever way the chain flips, so the atom's nickel-neighbor count is fixed even though the coloring is not. Columns with three or more undecided balls are different. Choices there no longer travel along a single chain, and that is the kind of structure from which hard instances can be built. So a useful way to measure a real puzzle is to ask how many undecided balls each column has after the obvious deductions.

I ran the obvious deductions on three particles from the dataset, using ideal photos along the three axes. The particles go by the labels p5, p7 and p11 in the original data. Particle Atoms Fixed by deduction Still undecided Most undecided balls in one column p5 4,281 2,623 1,658 13 p7 6,435 3,189 3,246 15 p11 10,589 2,141 8,448 21 In all three particles, every undecided ball lies in at least one column that still has three or more undecided balls. The easy regime of independent chains covers none of them. Columns with exactly two undecided balls do exist, but they are rare: p5 has 161 of them against 854 columns with three or more. So by the measure from the last section, real particles are far from easy. And yet an off-the-shelf integer programming solver answers every question in this post exactly, usually in under a second for p5 and in a few seconds for p11. The worst case is hard, and these particular instances are well inside the region where hardness is possible, but they are not the adversarial puzzles a hardness proof constructs. The per-atom picture for p5 shows the same split. Here I use a slightly stricter definition of a surface atom than in the next section. Of the 824 surface platinum atoms under this definition, 205 have their nickel-neighbor count settled by the obvious deductions alone. Another 19 are settled by the chain trick, where two neighbors on the same chain always take opposite colors. The remaining 600 need the solver.

The original study estimates how strongly each surface platinum atom binds OH with a simple formula. The formula looks at the atom's neighbors: how many are platinum and how far away they sit, and how many are nickel. Each nickel neighbor is weighted by how many neighbors it has itself, which mostly tells you whether it sits on the surface or just below it. Against the authors' more detailed machine-learning estimates, the formula is off by about 0.10 eV per atom on average. For every surface platinum atom, I computed the lowest and highest value this formula can take over all colorings that match the three photos. These are exact ranges. Two particles had the formula data I needed, and they behave very differently.

p5 p11 Surface platinum atoms 875 1,683 Binding energy fully determined 26% 9% Typical (median) uncertainty 0.04 eV 0.14 eV Uncertainty larger than the formula's own error (0.10 eV) 19% 61% Pairs more than 0.15 eV apart whose order is proven 99% 88%

The last row needs one sentence of explanation. Comparing two atoms adds up two errors, so the formula cannot reliably separate atoms whose values differ by less than about 0.15 eV anyway. Among the pairs it can separate, three photos prove the order for 99% in p5 but only 88% in p11. These percentages are lower bounds, because I only counted a pair as proven when the two ranges do not overlap at all. A fourth photo along a face diagonal changes the picture for p5 completely. For five of the six possible diagonals, every surface atom's binding energy becomes fully determined, and the sixth gets to 99%. For p11, the obvious deductions with a fourth photo fix only 260 to 380 more atoms out of more than 8,000 undecided ones. I have not computed exact energy ranges for p11 with four photos, because the solver gets much slower there. My guess about why p11 is so much harder: it is more than twice the size of p5 and much richer in nickel, 37% against 20%, so its columns hold more undecided balls.

The two arrangements from the first paragraph live in p11, around surface atoms 3186 and 2363 in the original numbering. Both are platinum, both have nine neighbors, and in both arrangements each of them has exactly two nickel neighbors. The difference is where those nickel atoms sit. In the first arrangement, atom 3186's nickel neighbors are on the surface and atom 2363's are below it. The second arrangement roughly swaps this. The formula treats nickel below the surface as weakening OH binding more, so the preferred site flips. In the first arrangement 3186 binds more tightly by 0.105 eV, and in the second 2363 does, by the same amount.

Both arrangements match all three photos exactly and have the same total composition. They differ from the published reconstruction in 16 and 24 atoms respectively. The swing of 0.21 eV is larger than the roughly 0.15 eV the formula can resolve for a pair. One caveat matters here: all of this is the formula's verdict. I have not checked the flip with a full quantum-chemistry calculation.

Everything above uses ideal photos, where each column's nickel count can be read off exactly. Real electron micrographs are blurry and noisy, which is one reason the original study needed more than fifty angles. I also tried to read these local differences from the actual photos. I kept the atom positions from the full reconstruction and asked only about the elements. The results were mostly negative. I could not tell whether a particular platinum atom had one or two nickel neighbors. Among 356 pairs of atoms whose order is certain from ideal photos, the real photos settled none. Comparing whole arrangements worked better. For the opening example, 35 of 48 real photos fit the first arrangement better than the second. So the real data do push back against the arrangement in which the preferred site flips. My image model was simple, and the original authors use a more detailed one with separate settings for each element. I suspect that is the main limit, but I have not tested it. So the ideal-photo results tell you what information the photos could contain. Whether today's photos let you read it out at the level of single atoms is still open.

Data and references • Yang et al., Atomic-scale identification of active sites of oxygen reduction nanocatalysts, Nature Catalysis (2024): https://doi.org/10.1038/s41929-024-01175-8 • Public data and code from that study: https://github.com/AET-Nanocatalysts/Pt-Alloy (I used commit 63081bbc8dd32ce7fbb2107f8a3c16ca643bd7ce) • Gardner, Gritzmann and Prangenberg, On the computational complexity of reconstructing lattice sets from their X-rays, Discrete Mathematics 202 (1999): https://doi.org/10.1016/S0012-365X(98)00347-1