Sometimes, the way humans phrase something makes the underlying logic needlessly complex, even though it makes perfect sense for us.

Annoyingly, the added logical complexity takes more time and effort in code than it does for a human to understand it, which leads to "human logic" sometimes making certain twists and bends (because it's not that hard for a human to take it into account), without considering how much more effort this may require in coding terms.
Tangentially, this is what makes government IT projects so difficult. Most governmental rules and regulations grew organically based on what made sense to the humans who discussed it at the time. The government doesn't hire a logician to refactor their rules for simplicity.

• A company has a list of departments, and a list of available phone numbers.
• A department has one phone number, and this phone number must be part of the company's list of available phone numbers.

This makes sense on a human level, but on a logical level, there's some duplication going on. You're registering the same phone number twice.

Having more than one source of truth inherently opens the door to all the effort that goes into making sure the sources of truth are synced up, and who to trust when they contradict one another.

It is significantly more efficient to change your approach so that there is only one source of truth, because this bypasses the need for making sure everything stays in sync with one another.

To that end, it makes more sense to rephrase your requirements. In the end, it will look the same to the end user, but the internal implementation can be changed to make things easier on you:

• A department has one phone number.
• A company has a list of departments, and a list of additional phone numbers.
• The company should have an "all phone numbers" property which is the combination of all of its departments' phone numbers and the company's additional phone numbers.

Note that the last bullet point could also be an implementation on the UI level. It depends on where you need to be able to access a full list of phone numbers.

It looks exactly the same to a user, but now you don't have to write any validation logic, nor do you open yourself up to having contradicting sources of information.

Although this invariant exists, I have decided to model Company and Department as separate aggregate roots

If the sole reason for splitting these into two aggregate roots was because of this phone number duplication; the above approach avoids this issue and renders the need to separate your aggregate roots moot.

[From your comment] No, a department should always be inside a company

This further suggests that you should not have split these into two aggregate roots.

Sometimes, the way humans phrase something makes the underlying logic needlessly complex, even though it makes perfect sense for us.

Annoyingly, the added logical complexity takes more time and effort in code than it does for a human to understand it, which leads to "human logic" sometimes making certain twists and bends (because it's not that hard for a human to take it into account), without considering how much more effort this may require in coding terms.
Tangentially, this is what makes government IT projects so difficult. Most governmental rules and regulations grew organically based on what made sense to the humans who discussed it at the time. The government doesn't hire a logician to refactor their rules for simplicity.

• A company has a list of departments, and a list of available phone numbers.
• A department has one phone number, and this phone number must be part of the company's list of available phone numbers.

This makes sense on a human level, but on a logical level, there's some duplication going on. You're registering the same phone number twice.

Having more than one source of truth inherently opens the door to all the effort that goes into making sure the sources of truth are synced up, and who to trust when they contradict one another.

It is significantly more efficient to change your approach so that there is only one source of truth, because this bypasses the need for making sure everything stays in sync with one another.

To that end, it makes more sense to rephrase your requirements (or, more precisely, changing your technical interpretation of the existing requirements). In the end, it will look the same to the end user, but the internal implementation can be changed to make things easier on you:

• A department has one phone number.
• A company has a list of departments, and a list of additional phone numbers.
• The company should have an "all phone numbers" property which is the combination of all of its departments' phone numbers and the company's additional phone numbers.

Note that the last bullet point could also be an implementation on the UI level. It depends on where you need to be able to access a full list of phone numbers.

It looks exactly the same to a user, but now you don't have to write any validation logic, nor do you open yourself up to having contradicting sources of information.

Although this invariant exists, I have decided to model Company and Department as separate aggregate roots

If the sole reason for splitting these into two aggregate roots was because of this phone number duplication; the above approach avoids this issue and renders the need to separate your aggregate roots moot.

[From your comment] No, a department should always be inside a company

This further suggests that you should not have split these into two aggregate roots.

Sometimes, the way humans phrase something makes the underlying logic needlessly complex, even though it makes perfect sense for us.

Annoyingly, the added logical complexity takes more time and effort in code than it does for a human to understand it, which leads to "human logic" sometimes making certain twists and bends (because it's not that hard for a human to take it into account), without considering how much more effort this may require in coding terms.

• A company has a list of departments, and a list of available phone numbers.
• A department has one phone number, and this phone number must be part of the company's list of available phone numbers.

This makes sense on a human level, but on a logical level, there's some duplication going on. You're registering the same phone number twice.

Having more than one source of truth inherently opens the door to all the effort that goes into making sure the sources of truth are synced up, and who to trust when they contradict one another.

It is significantly more efficient to change your approach so that there is only one source of truth, because this bypasses the need for making sure everything stays in sync with one another.

To that end, it makes more sense to rephrase your requirements. In the end, it will look the same to the end user, but the internal implementation can be changed to make things easier on you:

• A department has one phone number.
• A company has a list of departments, and a list of additional phone numbers.
• The company should have an "all phone numbers" property which is the combination of all of its departments' phone numbers and the company's additional phone numbers.

Note that the last bullet point could also be an implementation on the UI level. It depends on where you need to be able to access a full list of phone numbers.

It looks exactly the same to a user, but now you don't have to write any validation logic, nor do you open yourself up to having contradicting sources of information.

Although this invariant exists, I have decided to model Company and Department as separate aggregate roots

If the sole reason for splitting these into two aggregate roots was because of this phone number duplication; the above approach avoids this issue and renders the need to separate your aggregate roots moot.

[From your comment] No, a department should always be inside a company

This further suggests that you should not have split these into two aggregate roots.

Sometimes, the way humans phrase something makes the underlying logic needlessly complex, even though it makes perfect sense for us.

Annoyingly, the added logical complexity takes more time and effort in code than it does for a human to understand it, which leads to "human logic" sometimes making certain twists and bends (because it's not that hard for a human to take it into account), without considering how much more effort this may require in coding terms.
Tangentially, this is what makes government IT projects so difficult. Most governmental rules and regulations grew organically based on what made sense to the humans who discussed it at the time. The government doesn't hire a logician to refactor their rules for simplicity.

• A company has a list of departments, and a list of available phone numbers.
• A department has one phone number, and this phone number must be part of the company's list of available phone numbers.

This makes sense on a human level, but on a logical level, there's some duplication going on. You're registering the same phone number twice.

Having more than one source of truth inherently opens the door to all the effort that goes into making sure the sources of truth are synced up, and who to trust when they contradict one another.

It is significantly more efficient to change your approach so that there is only one source of truth, because this bypasses the need for making sure everything stays in sync with one another.

To that end, it makes more sense to rephrase your requirements. In the end, it will look the same to the end user, but the internal implementation can be changed to make things easier on you:

• A department has one phone number.
• A company has a list of departments, and a list of additional phone numbers.
• The company should have an "all phone numbers" property which is the combination of all of its departments' phone numbers and the company's additional phone numbers.

Note that the last bullet point could also be an implementation on the UI level. It depends on where you need to be able to access a full list of phone numbers.

It looks exactly the same to a user, but now you don't have to write any validation logic, nor do you open yourself up to having contradicting sources of information.

Although this invariant exists, I have decided to model Company and Department as separate aggregate roots

If the sole reason for splitting these into two aggregate roots was because of this phone number duplication; the above approach avoids this issue and renders the need to separate your aggregate roots moot.

[From your comment] No, a department should always be inside a company

This further suggests that you should not have split these into two aggregate roots.