> How would they be able to satisfy themselves that we had in fact sent "the original"

Well, for starters, they might determine that there is no other version of the painting on Earth or nearby that is said to be "the original".

They could additionally investigate the chain of custody of "the original" as far back as is feasible. It's getting hard to fool investigators here-and-now about these sorts of things; a sufficiently advanced interstellar civilization could have all sorts of additional investigative tools at its disposal.

This is simply accepting the premise that aliens have a preference for the oldest purported original over the most recent exact forgery, or alternatively have a preference for not being deceived and if promised the original want the original. If they don't care about acquiring the original, then maybe the forgery doesn't have to be that exact. "It's so exact that they should not care" is simply shifting the "that exact" line around a bit; physics doesn't quite let you abolish "provenance". Or, more finely, having promised to deliver "the original", if the seller ships "a perfect copy", has the seller committed fraud?

This is all hypothetical anyway; we have no evidence for aliens of any sort, let alone ones that want to acquire a human artifact for whatever reason. Imagining aliens sharing our own peculiar preferences with respect to art, but not granting that individual humans have different peculiar preferences, is the real problem in this thread. I don't think imagining yet more Star Trek technology is especially enlightening, but at least it's a little interesting.

Small nit:

> If you take one atom and replace it with another

This is a bit sloppy; for your argument you want to replace it with an identical atom -- no swapping of isotopes etc. -- and in an identical state with respect to its neighbours. Already historians do studies of Cs, Sr etc. isotope ratios at various depths, to study the mid 20th century history of various artifacts. They are already quite good at determining on which continent a painting was displayed or stored (or fabricated) at various times during 1945-1963.

Arguendo, the technology exists to make a "perfect copy" of an object like the Mona Lisa painting that is _locally_ indistinguishable in principle from the original. Arguendo, interstellar art forgery is profitable use of this technology. Arguendo, the knowledge of the technology and its utility in forging art is unknown to to the aliens, even though they know about the Mona Lisa and want it (that is, the one "universally" believed to have been painted by Leonardo da Vinci) rather than some traditional form of copy (that is not as perfect). That is, they care about provenance, but have not been offered (and have thus not rejected) a "perfect" copy in your sense.

The issue here is that provenance relates to the worldlines of the constituents of the macroscopic painting and whether they all converged around Leonardo da Vinci, for instance, rather than not converging around Leonardo da Vinci, but converging around the forgery machine. Since humans do not see macroscopic objects as worldtubes, human physicists are continually at risk of falling prey to a sort of slicing/threading chauvinism. In particular, the risk is that we assume that since electrons have spacetime-position independent (and covariant) characteristics, only those characteristics matter in a system involving multiple electrons. (cf. ideally we want to avoid considering large numbers of small contributions).

Boiling that down a bit, I think you're arguing in this thread that we should only consider some "present" values surface (e.g. one in which the aliens begin a test of all the traits of the Mona Lisa painting with those they have come to learn through research) and that everyone can and will ignore the surfaces on one timelike side of that.

Take the spacelike hypersurface on which the perfect copy and the original both exist but the copy only exists in one of the adjacent spacelike hypersurfaces. I think you are essentially arguing that the only choices of gauge on that surface all throw away (as "redundant degrees of freedom") the information necessary to reconstruct hypersurfaces on the "no copy exists" side, forming an information horizon.

(Geroch has a few things to say about this sort of argument in various papers, given the mild assumption of hyperbolization, and there is a wider literature on the initial values / Hamiltonian formulation of General Relativity. To be clear, I don't think you necessarily need recourse to O(h^n), n > 1 effects to poke holes in a formalization that imposes information loss; you get it only from the causal structure of a Lorentzian manifold with a tiny handful of mild additional constraints, all of which are well supported experimentally.)

Accepting for the sake of argument that a perfect copy in your sense can be made, I'd agree in an instant that we do not have the in practice ability to distinguish between copy and original if we threw both into a tumble dryer and ran the latter inside a thick-walled lead box for a couple of hours. I'd accept that nature with its Gauss-Laws provides similar (partial[1]) screening of "provenance", even. However, I'm not sure I'm convinced that a sufficiently advanced alien society could not see through these in principle, given enough effort; here we could add yet more Star Trek technology in the form of transporters, scanners, extremely long range telescopes ("enhance!"), FTL travel, etc.

Finally, if neither party can see through these in practice, the salient point is that at least one forgery exists, as does an effort by the seller of the "original" Mona Lisa to make it maximally difficult to tell that that forgery is a forgery. Caveat emptor.

- --

[1] Distinguishing between information conserving systems and Hawking's semiclassical information-destroying black holes.