Giving Mars a breathable atmosphere that will last for more than a few thouand eyars seemss to be impossible, and thus terraforming Mars would seem to be a waste of time and resources unless it could be done in a lot less than a few thousand years.
Unless the terraformers of Mars cheat, and find a loophole in physics.
So in part one of my answer I discuss the properties of a humanly brethable atmosphere.
In part two I discuss how long Mars could retain a humanly brethable, and demonstrate that that it would impossible for Mars to retain it for more than a few thousand years.
And in parts there, four, and five I discuss a few loopholes which could be used in stories about terraformning Mars.
Part One: A Breathable Atmosphere.
I am not certain that a lot of nitrogen is necessary for a breathable atmosphere.
In mountaineering, the death zone refers to altitudes above a certain point where the pressure of oxygen is insufficient to sustain human life for an extended time span. This point is generally tagged as 8,000 m (26,000 ft, less than 356 millibars of atmospheric pressure).1 The concept was conceived in 1953 by Edouard Wyss-Dunant, a Swiss doctor, who called it the lethal zone.2 All 14 peaks above 8000 m in the death zone are located in the Himalaya and Karakoram of Asia.
Humans have survived for 2 years at 5,950 m (19,520 ft) [475 millibars of atmospheric pressure], which appears to be near the limit of the permanently tolerable highest altitude. At extreme altitudes, above 7,500 m (24,600 ft) [383 millibars of atmospheric pressure], sleeping becomes very difficult, digesting food is near-impossible, and the risk of HAPE or HACE increases greatly.
Even using bottled oxygen, mountain climbers in the death zone have a high risk of death. If someone is injured in the death zone, the rule is to leave them to die instead of dying trying to save them. A few mountaineers have climbed Mount everest and returend safely without bottled oxygen, but those who try have an even higher death rate than the ones who use bottled oxygen.
There is a scientific study of what is necessary for a planet to be habitable for humans. Habitable Planets for Man, Stephen H.Dole, 1964.
Atmospheric requirements are discussed on pages 13 to 19.
On page 19 Dole sums up human atmospheric requirements as oxygen between 60 and 400 mmHg and carbon dioxide between about 0.05 and 7 mmHg. And there must be some Nitrogen in the atmosphere for plants. Dole discusses surface water on pages 19 to 20, and where there is surface water, there is also water vapor in the atmosphere. Table 4 on page 21 says the maximum pressure of water vapor should be 25 mmHg.
I note that the average Martian atmospheric pressure is 4.5 mmHg, almost all carbon dioxide, which sems to be within human tolerance. In the lowest place on Mars, the atmospheric pressure is as high as about 11.6 mmHg, and almost all carbon dioxide, so getting rid of some of the carbon dioxide in that region would be necessary for humans to breath there.
The minimum atmospheric requirements as described by Dole would be an almost pure oxygen atmosphere, similar to the low pressure but pure oxygen atmospheres in the Apollo 1 fire and other space program fires. actually the Apollo ! fire happened when the cabin atmosphere was pure oxygen and higher than sea level pressure on Earth. There would be much lower fire risk with a much lwer density pure oxygen atmosphere.
Diluting the oxygen with nitrogen and other inert gases to reduce fire risk would be a good idea. The minium breathable atmosphere according to Dole would have a little nitrogen, carbon dioxide, and water vapor, but I don't know if they would be enough to reduce the fire risk to acceptable levels. That is something that a person designing a fictional atmsophere should look up.
Humans can tolerate a lot of nitrogen in the atmosphere. Other answers have discussed getting nitrogen out of the Martian soil and rocks, and whether there is enough nitrogren on Mars.
I note that the main sources of gaseous nitrogen in the solar system are the atmospheres of Earth and Titan. If Titan is lifeless there would no objection to transporting a lot of its nitrogen to Mars.
Transporting a lot of nitrogen from Titan to Mars would be a big project, but terraforming a planet is a big project.
Nitrogen can form many compounds, including ammonia. Most of the small dwarf planets, moons, comets and other objects in the outer solar system are made of mixtures of rocks, and ices, ices including not only frozen water but other substances, including frozen ammonia. So it might be easier to transport nitrogen from small outer solar system bodies than from Titan in the gravity well of Saturn.
Other gses that humans can tolerate about as much of as they can tolerate oxygen, or in some caases more of, are krypton, argon, neon, and helium. The noble gases could be taken from the atmospheres of giant planets, but it would take a lot of energy to escape from the giant palnets.
Part Two: Retaining an Atmosphere.
Before someone considers increasing the atmosphere of Mars, they should find out how long Mars can retain the gases they introduce into its atmosphere. The heavier an atom or molecule of gas is, the slower it will move at a specifc temperature.
Dole discusses gas capture and retention on pages 33 to 39. Onpages 34 to 35 Dole discusses a rule of thumb for calculating a planet can retain a gas in its atmosphere, or to be precise, how long it will take for the amount of gas to drop to 1/e, or 0.368, of its original amount.
Table 5 on page 35 shows that if ratio of the escape velocity (whch is not the same as the surface gravity) of a world divided by the root mean-square veloity of a gas is one or two, the retention time will be zero, if the ratio is three, the retentintime will be a few weeks, if the ratio is four, the retenti time will be a few thousnd years, if the the ratio is five, the retention time will be about a hundred million years, and if the ratio is is the retention time will be about infinite.
So increasing the ratio of the escape velocity to the root-mean-square velocity of a gas by four times, from a ratio of two to a ratio of six, will increase the retention time from zero to infinite.
At a specific temperature, the heavier gases will have slower root-mean-square velocities than the lighter gases, and thus will be easier to retain. According to table 6 on page 38, most of the gases we would be interested in having in a breathable atmomsphere have atomic weights similar to those of atomic and molecular nitrogen and oxygen. Molecular n\Nitrogen and oxygen have twice the atomic weights of atomic nitrogen and oxygen.
On page 54 Dole says that gases escape from planets from the uppermost atmospheric layers, their exospheres. The exospheres of planets tend to have much higher tempertures than the surface temperatures of planets, meaning that gases move much faster in the exospheres than near the surfaces. Ultraviolet radiation from the sun and other stars, breaks up a lot of molecules in the exospheres of planets into separate atoms, which travel faster than molecules.
Dole says that Earth has an Earthlike temperature at the surface, and the temperatures in the exosphere of Earth frange from 1,000 degrees Kel in to 2,000 Kelvin. Dole says that if a world could have warm enough temperatures at the surface for humans, while having an exosphere temperture no higher than 1,000 degrees K, where the root-mean-square velocity square velocity of atomic oxygen would 1.25 kilometers per second, it would need an escape velocity five times that, or 6.25 kilometers per second.
So Dole calculates the minimum escape velocity as 6.25 kilometers per second. According to Dole's calculatins for the relationships between mass,diameter, and other properties of a planet, that would require a planet with 0.195 the mass of Earth, a radius of 0.63 Earth radius and a surface gravity of 0.49 g. I note that different combinations of mass and diameter could produce the same escape velocity. Dole didn't believe such a small planet could be able to produce a dense oxygen rich atmsphere, but that doesn't matter, since the question is about artifically producing a new atmosphere for Mars.
An escape velocoity of 6.25 kilometers per second would enable a world to retain 0.368 of its original oxygen for about 100 million years. An escape velocity six times the root-mean-square velocity of atomic oxygen at 1,000 degrees Kelvin (7.50 kilometers per second) would be better, enabling he world to retain atomic oxygen at 1,000 degrees Kelvin for an infinite time.
If a world needs to have exosphere temperatures higher than 1,000 degrees Kelvin to have a warm enough surface temperature for humans, the exosphere velocity of oxygenw ould be higher and higher escape velocities would be needed to retain oxygen for those periods of time.
The escape velocity of Mars is 5.027 kilometers per second, the mass is 0.107 Earth, the radius is 0.532 Earth, and the surface gravity is 0.3794 g. An escape velocity of 0.5027 kiloemers per second 1.0054 times an escape velocity of 5 kiloemters pr second, and 0.804 tiems an escape velocity of 6.25 kilometers per second. So if the exosphere temperatue of Mars was as low 1,000 degrees Kelvin, the secape velocity of Mars would be a lot closer to the value that would retain 0.368 of the oxygen for a few thousand years than the value to retain 0.368 of the oxygen for about a hundred million years.
So unless the terraforming process can produce a sufficient oxygen atmosphere in much less than a few thousand years, Mars would be losing oxygen faster than it could be produced.
On the bright side, there are more complex formulas for calculating the atmospheric retention time. A complex mathematical model of the atmospheric compositon of a world might produce a longer or a shorter period to retain 0.368 of a gas than Dole's formula. So someone could learn those formulas and see if they can make a Martian astmosphere last longer.
On the pessimistic side, it is quite possible that the exosphere temperatur ure of Mars would have to be much higher than 1,000 degrees Kelvin for Mars to have retain have surface temperature warm enough for liquid water and for humans.
The Martian escape velocity is only a little over 5 kilometers per second, which would be high enough to retain atomic oxygen at a temperature of 1,000 degrees Kelvin for only a thousand years few weeks. So it doesn't seem probable that different calculations could show that Mars could reatin oxygen for hundreds of thousands or millions of years.
And if warm enough surface temperatures on Mars would require exosphere themperatures a lot hotter than 1,000 degrees Kelvin, Mars would be able to retain oxygen for a lot less time.
And a another pessismistic factor is that worlds lose atmospherice gases by other processes, including combining with other supstances to make liquids or solids. In those cases the use of vast amounts of atomic energy could break up those compounds and release the gases back into the atmosphere.
But another important method of atmospheric loss over the span of billions of years, and maybe even millios of yearsis "sputtering", particles in the solar wind hittng particles in the upper atmopshere and knocking them into interstellar space. Those charged particles can be deflected by a planet's magnetosphere, but the magnetosphere of Mars shut off long ago, enabling the solar wind assist in the loss of the Martian atmosphere.
So I find it hard to believe that Mars could retain a dense and also breathable atmosphere for Billions or millions of years. Possibly for thousnds, tensof thousands, or hundreds of thousnads of years. But the factors which make an atmosphere breathable put strong limits on its composiiton and how long it can be retained.
So what I say to anyone who talks about terraforming Mars is "Put a lid on it."
Part Three: The Roof of the World.
Literally put a lid (or a roof) on it (Mars).
Putting a roof on Mars to retain the artifical atmosphere would be a vast project. But terraforming a planet is always going to be vast project unless someone can think of some magical way to sidestep all the necessary processes.
A roof over Mars would make it a type of a hypothetical shellworld.
There are four types of shellworlds, and three would be more or less useful in terrformng Mars.
A planet or a planetoid turned into series of concentric matryoshka doll-like layers supported by massive pillars. A shellworld of this type features prominently in Ian M. Banks' novel Matter.
A megastructure consisting of multiple layers of shells suspended above each other by orbital rings supported by hypothetical mass stream technology. This type of shellworld can be theoretically suspended above any type of stellar body, including planets, gas giants, stars and black holes. The most massive type of shellworld could be built around supermassive black holes at the center of galaxies.
An inflated canopy holding high pressure air around an otherwise airless world to create a breathable atmosphere. The pressure of the contained air supports the weight of the shell.
Any sort of roof around a terraformed Mars would need to have giant airlocks to let spaceships land and take off. And possilby airlocks surouunding the bases of Martian beanstalks used to trasport cargos of atmospheric gases down to the surface.
Anyone with imagination should be able to think of story ideas involving building a roof over Mars, and about mega disasters happening on a roofed Mars and techiques to prevent them.
Part Four: Force Fields.
In a more space opera type setting, possbily someone has invented forcefields capable of stopping fast moving gas atomsand molecules. Thus giant force field generators would be necessary to enable Mars to retain its atmosphere long enough for terraforming it to be a viable project.
Imagining stories relating to those force field generators should be easy.
Part Five: Artifical Gravity Generators.
And In a more space opera type setting, there could be artifical gravity generators installed on Mars, which would increase its surface gravity as a minor effect, and which would be intended to increase its escape velocity enough for Mars to retain its artifical oxygen atmosphere for long enough to make terraforming Mars worthwhile.
There is an old space opera The Legion of Space (1934) by Jack Williamson, where many worlds in the solar system, some as small as Phobos, have been given artifical atmospheres retained by artificial gravity generators.
And obviously artifical gravity generators suggest all sorts of story ideas.